Ecaxtly what ianm said.
Customer service is key.
There's no point in getting a good hosting package in terms of space and add-ons if when you need help and need to contact the host it takes them 2 weeks to reply.
SiteHQ are very fast in resolving my issues, normally only taking a couple of hours to respond and are always helpful.
I would search around.
Webhosting Talk is a good starting point. There are lots of hosts around and its often a place where people will share experiences and give advice.