A search engine starting from scratch is a huge task, which is not made easier with the brand recognition the big guys get. Since search is such a fundamental concept to the use of the web, many people think of it as a start point to the internet. This is where its hard to get early adopters because only people specially interested in new SE's would try the new kid, everyone else uses the comforting familiarity of Google.

And lastly, the leaders in the search space are some really big names. Names which have gone onto become verbs. To go head on against such competition is commendable if you're not in the vertical market. What is even tougher when the media calls you a *-killer and in the initial days you can't live upto the false hype that is created (see Cuil).