(May 2013) I've contacted Google and this is their response:
Thanks for contacting us about country support for Google Play.
We use the billing address of your default payment instrument in Google Wallet to help determine your home country for accessing the Play Store. Our collection of content can vary by country, so your view of the Play Store may differ from what others are seeing when you travel outside of the country listed on your default payment method's billing address.
Please note that you must have a valid payment method with a billing address located inside a country in order to access that country's Play Store.
If you're having issues viewing your intended country's Play Store and would like to change your default payment method or update an existing billing address in Google Wallet, please use the following steps:
Sign into your Google Wallet account to manage your payment methods https://wallet.google.com/manage/paymentMethods
Add a new card or change your default payment instrument to one with a billing address located inside your desired country
Open the Play Store and navigate to any item available for download
Click to begin a download until you reach the "Accept and buy" screen (no need to complete the purchase)
Close the Play Store and clear data for the Google Play Store application (Settings > Apps > Google Play Store > Clear Data) or clear your browser cache
Re-open the Play Store. You should now see the Play Store that matches your default payment instrument's billing country.
If you haven't yet added a payment method to your account for the first time, please add a card directly from the Play Store with a billing address that matches your intended country location. Then, follow steps 3 through 6 to show your intended country's Play Store.
If you believe that you're experiencing a different location-related issue, please first verify if the country of your primary payment method matches your intended country. If the countries match, please provide any screenshots and additional details that might help me resolve your issue.
We appreciate your feedback as we continue bringing more content to Google Play. Thank you for reaching out!
(July 2015) Update
Due to the popularity of this answer, I've decided to add bits to this answer which others have pointed out to improve and update this answer.
- The Accept and buy screen is only available on desktop (not mobile) - thanks @fwuensche
- Google Wallet has changed since the original answer was posted, also try to change your address on these links - thanks @corbacho
- Settings
- Address Book
- Clear all cache and data from the Play Store app
- Try these steps of removing and adding back your account - thanks @Dushy
- Google customer support suggests it may take between 30 minutes to 24 hours for the address on the account to refresh.