Competition proves there is a large market and others are investing significant time and money into that niche. I know two local areas that have a Starbucks AND Dunkin Donuts within 100' from each other. In one case the drive thrus are directly are across a narrow street. When they closed some Starbucks in my area, those stores remained, despite being near competition.
The trick is to create an IMPROVEMENT on something that is already there. Innovation is probably very unlikely. Even in programming, you want to build off something that is already established rather than starting from scratch. Rails, Wordpress, CodeIgnitor, .Net, etc are all starting points for creating a new and innovative web service.
In 2005, it was hard to believe how big MySpace was. In the span of a few years an improvement to their service ate them alive. In 1995, AOL probably had many millions of members, and at the time there was little to no competition. If they played their cards right they could have done the same as Facebook, but they didn't.
Look at Etsy - who in their right mind would think they can compete against Ebay a few years ago? They are doing pretty well now. That service is far from innovative.
If something comes along that offers a better search experience than Google, they will be in for a tough ride in a few years. When Google started they were competing against companies during the dot com boom that had billions in disposable cash. Those are pretty much gone now, or at the brink of absorption. Search was far from an innovation. There were primitive internet search services in 1990.
Moral of the story: Instead of thinking of the next big idea, think of how you can improve something that exists and give people what they want. Look at every web service you use and keep an open mind. Now you go from saying "Its all been done" to "There are thousands of possibilities for improvement."
Also, there is a quick way to find how big your market is:
Google Keyword Tool
Put in some keywords and get an instant view of how many people are "hungry" for that type of product/info.