The same thing happens for app purchases, it happened to my while moving country. At the same time, I did not have any problem with the Windows Store or Google Play.
Windows Store used to be extremely bad pre-Windows 8 - I live in Uruguay and it basically didn't work unless you lied repeatedly about your location, age, etc., and required several factory resets (that was my experience with a Nokia Lumia 800).
It turned me off Windows as a mobile OS, but from what you're saying, it seems they've cleaned up their act now.
