If that error message is correct,
then I can only suggest that you purchase the cheapest gift card that you can find, do some research and purchase apps that are exactly that amount + the 0.17
Why do you need to change stores?
Usually to create an account in a new country, you are required to provide a residential address in that country.
Have you moved or something?