J'ai eu le même problème, et après avoir cherché partout, je suis allé voir mon fournisseur de services (en Colombie) et la solution était vraiment simple, mais pas évidente du tout.
Tout d'abord, laissez-moi vous expliquer comment les services fonctionnent ici. Nous avons ce qu'on appelle des "plans fermés" et des "plans ouverts". Avec les plans fermés, vous payez une somme fixe et mensuelle pour votre service, avec les plans ouverts, vous avez une redevance mensuelle aussi, mais vous êtes autorisé à dépasser votre redevance dans le cas où vos minutes ou le plan de base est dépassé, contrairement au plan fermé.
Il semble donc que pour vérifier votre numéro de téléphone, Apple prélève une petite somme d'argent sur votre compte, environ 10 cents. Donc, si votre plan est ouvert, vous n'avez aucun problème, mais (comme dans mon cas) si votre plan est fermé, Apple est incapable de vérifier votre numéro.
Dans mon cas, j'ai pu facturer à mon plan quelque chose comme 30 cents et voilà ! le numéro a été vérifié et tout est redevenu normal. L'agent du service clientèle m'a dit que chaque fois que je voyage dans un autre pays et que je reviens, je dois m'assurer que j'ai de l'argent dans mon forfait pour qu'Apple puisse vérifier mon numéro. Je sais que cela peut paraître bizarre, mais après avoir tout essayé (même restaurer mon téléphone et changer la carte SIM), c'était la seule solution.
Je ne sais pas comment ça se passe avec votre fournisseur d'accès, mais dans mon cas, ça a marché !