RaphMac, só o iCloud ou a App Store também? Adicionou algum Gift Card em sua conta recentemente?
Contato via telefone acho que vai ser meio complicado, acho difícil conseguir.
Dica: resolvendo o caso, crie um e-mail no gmail e configure ele para puxar todos os do iCloud. Funcionará como uma espécie de backup.