Flump works I think. Has very good PHP settings with full functionality. http://www.flump.net/ Claranet works as well but is expensive.
www.oneandone.co.uk Ok not the cheapest but at least they answer the phone Plus both php and html coop works for me
www.webfusion.co.uk - £7.99 pm with 1 mysql database and php etc. Very reliable. www.domainrush.net - £30 pyr with mysql database, php etc. Very reliable.
I would go with http://www.web-hosting.uk.com/. Why? I had a great customer service experience with them - and I don't even use them or live in the UK! I was having problems getting my host to set up my server to run the Co-Op ads. I contacted one of the users on this board (g00gl3r) who mentioned that he managed to get the script to work on a WIN server. He gave me his host name, and I sent them an email. One of their tech Guru's, Johnny Baird, emailed me back with a few more questions, then promptly replied with the answers that I needed to give my own web host on the proper server settings. Most hosts have reliable servers - customer service is what makes the difference. These guys passed the test in my book.
you shouldn't have to ask your host to be able to run anything specific php wise, unless its insecure to the box (other users sharing the box), its something that should be able to run anyway. Personally i'd go with www.catalyst2.com i run all my sites with them and havne't had a problem yet. Just remember you get what you pay for, if your thinking of paying something like £30 a year then i'd go with the ones above, but if you want a proper host, i wouldn't settle for anything like that and go for something around the £15 - £50 a month marker for shared, and around the £100 - £200 for your own box.