cheap is not always cheerfull when it comes to hosting, there's a lot of "wanna be hosts" a few things to check first would be
1. do a whois on the domain see how long it's been registered, it will give you an idea how long they have been going.
2 check forums like
www.forum2.co.uk and
www.webhostingtalk.com
3. never ever ever use a company called eukhost.com just read the thread on forum2.co.uk and you will see what I mean.
And if you really get stuck I have a reseller account and can set you up with some space