Hi philm, thanks for the pointer.
I just managed to sort the problem out (by accident, but I'll take whatever I can :-)
I went to the iTunes Music Store on my Mac and tried to buy something. Turns out that this store was pointing to the US store as well (which makes sense, as the iPhone takes its cues from iTunes on the computer). When I tried to buy something there (as a test), I got a dialog saying the same thing as I got on my iPhone: my account was for the UK store. _This time_, though, I got the option to change to the UK store, which I did. I then sync'ed the iPhone, and viola, UK store all around.
Yay!
Buy why this UK bought Mac would point to the US store is a mystery. Oh well, problem solved.
Thanks again for the pointer.
Cheers!
Chas