Thanks - I did try that but I haven't been able to come up with any combination of location and regional settings that works on this phone. Even setting it to US everything doesn't work.
I have this problem also. Cortana either thinks I'm in America or that I speak Chinese, but I couldn't possibly be an American living in China :p
Did you check for updates in store and settings after changing region and language to UK? I made it work once and I'm not even in an English speaking country.
Have you got high precision location tracking on? For some reason this needs to be on all the time in order for you to have Cortana.