1.) Quality of Search-- In order to be successful, the quality of their search must be at least as good as Google (obviously it much more helpful if it's better). As many have noted, this clearly is not the case right now, and slightly complex queries such as "Linux search and remove multiple files" return zero results.
2.) Revenue Stream-- As noted above, it is going to be difficult for Cuil to break into the search market because they have to achieve such a high quality of search. But even if they are successful breaking into the market, how are they going to generate revenue? An Adsense like program? That's just another thing that they would have to do better then Google, and I just don't see both things happening.
3.) Overcoming Inertia-- Even if Cuil addresses 1 and 2, the moment of inertia of an average Google user is very high. Google has the best web mail available on the market, and along with all the other services Google provides, people will be reluctant to switch their searching to Cuil because everything else that they do will still be through Google.
I don't mean to be negative, and more power to these guys for taking on an area of the web that most people are afraid to even look at. But I guess I would say that if I were to plan a startup, I would probably pick a more advantageous slice of the market (probably one that doesn't exist at the time of planning). At the same time, you have to play your strengths as a programmer, and it seems like thats what the Cuil team is doing.