(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:
1) Sign into your Google Wallet account to manage your payment methods
https://wallet.google.com/manage/paymentMethods
2) Add a new card or change your default payment instrument to one
with a billing address located inside your desired country
3) Open the Play Store and navigate to any item available for download
4) Click to begin a download until you reach the "Accept and buy"
screen (no need to complete the purchase)
5) 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
6) 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
- If you're in a "family account", leave it
- 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.