I'd consider somewhere like
http://www.httpme.com first, which I currently use, as they have a good reputation and are reasonably priced. E.g. their plan 2 is $45/month and seems broadly similar to the place you mentioned, which costs £35.25/month. So HTTPME are cheaper and also have bigger plans you can move up to if needed.
Alternatively, a similar host to HTTPME is
http://www.bluewho.com - I'm not with them yet but may give them a go for my next set of sites. They're even cheaper, costing $30/month for a similar deal.
There may well be other places, too. A good place to look for info on hosts is
http://www.webhostingtalk.com - just search the forum for the web host you're considering and see what people have to say about it.
I've found that US hosts offer better deals (both in cost and facilities) than UK hosts and so long as your domain name ends in .co.uk Google is quite happy to list them as UK sites even though they're hosted in the US.