What do I do when my phone says “Apple ID is only valid in uk stores”?

Change your Apple ID country or region - https://support.apple.com/HT201389

You can only use the store for a country where you are resident as demonstrated by paying in the local currency and normally demonstrating such residency by entering a valid payment method billed to a physical address in that country. In other words, you cannot use dollars in the UK store.

See - Change your Apple ID country or region - Apple Support

Do you have any current subscriptions in the UK? Do you have any UK store credit?

Have you tried going to settings, iTunes and App Store, tap on your AppleID and sign out, then sign back in?

I don't know if these still apply:

[Note: the two documents below have been changed by Apple in late 2017 and no longer contain the information quoted.]

App Store [for iOS devices] Frequently Asked Questions (FAQ) - http://support.apple.com/kb/HT2001 when using iTunes --> "To change countries, scroll to the end of the iTunes Store home page and click the flag indicating the current country. To choose a different country, click the appropriate flag."

iOS: Changing the signed-in iTunes Store account - https://support.apple.com/HT204053 - Change your iTunes Store country: "Sign in to the account for the iTunes Store region you'd like to use. Tap Settings > iTunes & App Stores > Apple ID: > View Apple ID > Country/Region." (wording from old document; new document does not contain this information).