UK servers would be a bonus, although not essential.

I've heard a little controversy about Hostgator but you get complaints with every service really. I'll have a Google :P

Tempted to go for one of these:
cPanel Hosting UK | Shared Linux PHP MySQL cPanel Hosting
https://dreamhost.com/hosting.html
The Best PHP Hosting: PHP 5.0, PHP 5.1, PHP 5.2, MySQL, PHP Tutorial, Free PHP scripts, Zend
https://www.krystal.co.uk/uk_web_hosting/