How to change my device location on the Play Store I'm trying to download an App on the Play Store, specifically the Vue Cinema app, but this app is only (presumably) available in the UK.

I have just relocated to the UK, so how do I set my location to be the UK?

I have updated my google+ settings to say that I am currently in the UK.

Also, my google account is a Google Apps account but I don't there is any location associated with Google Apps.
(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.