(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](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](https://wallet.google.com/manage/w/0/#settings:)
 - [Address Book](https://wallet.google.com/manage/#addressBook:)
 - Clear all cache and data from the Play Store app
 - Try [these steps](http://android.stackexchange.com/questions/44677/how-to-change-my-device-location-on-the-play-store/59552#59552) of removing and adding back your account - thanks @Dushy

-I just want to add that after contacting google today (06/08/2016), they made me aware that it takes from 30 minutes to 24 hours for the address on the account to refresh. So after changing that, one might consider waiting a while before trying again to access the play store.