WebFaction[1] is commonly recommended on Hacker News[2] for shared hosting. Their service uses cgroups, which gets rid of the traditional "bad neighbor problem" in shared hosting.[3]
This week I needed a shared hosting service for a low-traffic legacy PHP app and I chose WebFaction based on the recommendations on Hacker News.[2] I don't have enough experience with WebFaction to recommend it, but the experience I've had so far has been good. My account was ready roughly one hour after I signed up, and I successfully transferred the aforementioned PHP app to WebFaction very quickly.
You mentioned that you previously used a web host in the UK. WebFaction.com has servers in Europe (Amsterdam).[4]