Buenas, para cambiar de país, efectivamente es tal como lo estas realizando: Cambiar o eliminar la información de pago de tu ID de Apple - Soporte técnico de Apple, puede que tengas algún cargo en la cuenta anterior y por eso no te deje configurar de nuevo tu cuenta en otro país, comprueba el siguiente enlace: Si se rechaza el método de pago o tienes un problema de facturación con una compra anterior en el iTunes Store - Soporte….
Como anexo, comprueba que estés utilizando un método de pago valido: Formas de pago que puedes usar en el iTunes Store, App Store y iBooks Store - Soporte técnico de Apple
Si tras todo esto continuas con el problema, ponte en contacto con el soporte tecnico de Apple.
Un saludo.