Well - many may believe that the lowest price counts, but I tend to put a higher value towards support and technical capabilities.
An example: Here's a company that was burned by yahoo small business, due to mismanaged hosting. Open exploit in wordpress instance on a shared hosting environment allowed hacker to modify multiple websites with bad payload. One of the affected sites found and fixed the problem, but yahoo decided that the site owner was the hacker and blocked access to his site, email, control panel, etc. Couldn't talk to anyone - took 10+ days to reactivate things.
Now, was that 10 days downtime worth $10 less a month? For those hobbyist sites, most likely the answer is yes. For business? I doubt it.
back to the main question - following Simons answer, I would state that there are niche hosting markets - but only to those segments who are beyond the hobbyist stage and can understand the differences.
burstable vps'es with API interfaces are becoming interesting options for those who want a bit more persistence than what amazon provides. There's been some interesting atom based server advances (512 cpu / 10u / 2KW power draw) - perhaps leveraging that capital investment in some really primo virtualization schemes would bring returns.
Think about what you can offer -- are you a classic web host? or can you offer something very niche and value-added. Ie, how does a specific small business get information to their best customers (this is in the end what web hosting is about.. it is just means to an end).
You need to add a lot of value to make it work, but it can happen. I know because I run what is sort of a web hosting business, but not really because of all the value that I add for my customers.
I know that's not a very specific answer, but what I am saying is you should turn the question around and figure out what your potential customers wants and work backwards from there to what kind of solution you can provide. It sounds like you have a solution in search of a problem instead of the other way around.
With all the cloud offerings now, as well as sites that will host and make it easy create your own website, low-hanging fruit is going to be incredibly hard to find.
In order to compete you will either have to offer some incredible service and probably compete on price. Once you start in a market where you have to compete on price, as there is little else separating competitors, the newcomer will lose.
There are some areas that aren't being served, but that is because there isn't much of a need for it yet. For example, if you want to write enterprise apps that are cloud-based and written in Erlang, you are out of luck, as, though yaws is an incredible http server, scaling very well, very stable, there are relatively few Erlang programmers.
You may be able to find some people that want to, or have written, some very useful applications in functional-programming languages, and then you may be able to offer them a site, but you would need to show some relatively killer applications to get people moving toward those types of languages.
But, if you have a killer app in Haskell, and it starts to get attention, what stops Amazon from jumping into that area quickly, they have the money to do it.
You would need to build up tools or APIs that are proprietary but make development easier, as then you are offering something that others can't duplicate as quickly, but, you would then need to keep adding to your development suite, as, if you slow down, you will eventually be passed up.
While there is a "cloud" over all of us in the tradional hosting business, all hope isn't lost. You should look into a niche away from the technological aspect in order to find your special "brand". For example, you might try catering to extreme sports companies, and make a division of your brand about that. You can create individual landing pages for each market segment. Traditional hosting hasn't declined in years, you just need to find a way to gain a bit of traction. Embrace the technology you offer, and find a market that fits it. It's the recipe every succesful company follows.
That's my .02
The question is wrong. There is a definite niche - free high end clouding services. The problem is whether there is a niche where you can make money, and I fear the answer to that simply is no. You need a lot mof money, and the possibility to generate a lot of customers fast (existing other business, brand name - like amazon was able to do) to get the flow for justifying the investment.
Sorry, 10 years too late.
What @Tiago describes is managed hosting.
There's a huge opportunity for managed hosting wherein you target specific technologies and frameworks such as python/django or ruby/sinatra.
Make it easier/faster to deploy apps, provide more uptime (this has been a serious issue with Heroku), or target an upcoming platform such as Node.js.