In my case, what turned out to work in the end was to make an actual purchase.
In google wallet, I had updated all my information, as well as added a new card with my new address attached to it and set it as default. This in itself however didn't seem to be enough.
Later though, I read an article recommending us to actually purchase an app through Google Play using the new card - you'll need to wait for 15 minutes to complete the payment since that's the time you're allowed to require a complete refund.
Finally, I closed the Play Store and completely reset the Google Play Store application (i.e. go to Settings > Apps > Google Play Store, and click on Force Close, then Clear Data, and Clear Cache).
After that I could access things in Play that were only available to my new credit card's country, which previously I could not see due to regional restrictions.
Hope it helps you guys!