Hosting is difficult because it's not only over saturated - it's over saturated by extremely cheap and good options.
To be successful you have to do something different (it's unlikely you can compete with GoDaddy and friends on price).
You can go after small niches (for example - hosting for furniture stores*), by creating offers that are specifically tailored to the specific audience - especially if those are non-technical people that will have an hard time configuring the servers themselves - you can probably take over such a small market - then repeat for other small markets.
You can also go for a technical niche (example, best phpBB** hosting) - this will let you specialize in one thing and charge more money because you have the experts at the software you are hosting.
Or you try to specialize in support, if you make the signup process completely painless, give every new customer a lot of personal attention and help (this is the important part - this can't be automated) and of course give excellent support when something bad happens people will be willing to pay extra and will recommend you to their friends.
Anyway, the key is that you should differentiate, that differentiation doesn't necessarily changes the core service you are providing but without it you are just another commodity competing against $5/month services from big reliable companies.
* - I tried to pick an obviously bad example, don't blame me
if there's no market for furniture stores web hosting.
** - another obviously bad example, please please please don't
encourage any one to use phpBB
