Many people gained access to Google Music before it launched in their country by first accessing it from the US (sometimes via a VPN, EC2 instance, etc.). When Google Music launched "for real" in their countries, many (like me), found that that service believed they were in the US, and offered US-only services (such as All Access), and showed US-only offers, and prices in USD.

After many months of exchanging emails with Google Play support and trying all sorts of things, I was ultimately (and repeatedly) told they were aware of the issue, but did not yet have a fix :(

Recently, I was able to solve this issue, with the help from some info posted to an XDA-Developers forum by a poster named Movisman. Although the instructions didn't work for me as posted, it triggered a thought that lead to the fix. It actually turned out to be quite a simple fix:

Purchase a non-free track, using a card based on your home country as payment. Do not use Google Play credit!

All of my previous purchases had used the free credit that I got when I purchased my Nexus 7. As soon as I purchased a track using a UK card, the options for All Access vanished and all the recommendation prices changed from USD to GBP!

Since posting this fix in the forum, a number of other people have repeated this success. I'm posting it here in the hope it'll turn up in Google searches to help others. I've also notified Google Play support of how we fixed it (and provided a link to the forum) in the hope they can more quickly give a fix to anybody else reporting it.