One of the first things I wanted to do after moving was to switch my Google account's country to USA so I could play around with the US-only features on products like Google Now.
After searching for a while I couldn't really find much other than people saying to call them, so I did. Turns out it's all based on the billing address on Google Wallet, here is the process you follow to update your region without waiting.
Add a new card whose billing address is in the desired country
Open the Play Store and go an item available for purchase
Click through until you hit the "Accept and buy" screen, you don't need to press this
Close the Play Store and clear data for the Google Play Store app on your phone/tablet or clear your browser cache
Your account should have been updated to the new country. If you have any other apps that have country-specific features then be sure to clear their data too.