I believe this process has been improved in the last year to more easily change your country. I'm not sure when you went through it, but understand that it can be a complicated problems due to different regulations for payment related activity and digital goods. Like some countries Google is required to verify your tax id with the government to even buy 99 cent app.
I've now been living in the UK for six months and three months ago I had a 3hr phone call with a very lovely support lady that tried to help but we didn't manage to change it. She told me that maybe I could just open a new account but then I said that my whole life is on this account and that is not an option. If I have to start over I'd rather make sure this won't happen again.