Downtime was not a big issue for me at Bluehost/Hostmonster. Server performance tended to vary though, from decent to worrisome though.
Downtime can happen to any host/server.
but they are offen down.
How do you determine that they are down? Sometimes it's your ISP that's the problem. I suggest you try using a service like Pingdom (they have a free account too) to keep watching for downtime. Use the HTTP check, not the much simpler "ping".
Once you have a track record of downtime, contact the host, confront them with the evidence, and ask for the problem to be solved.