That's a barrier due to the intrinsic nature of the technology in question. It's not a barrier due to legal, political, social, etc difficulties.

Getting something up and running that has a good enough coverage of the web, constantly has fresh enough content, is able to catch up on sudden events (ie. Michael Jackson's death) and show relevant content within a maximum of a couple of minutes, is scalable and can handle the load if it becomes popular, has a low enough latency for the end user (a single server in a basement halfway around the world does not do the trick), AND offers something of significance that makes users actually want to change their habits and switch from their current search engine... Now, that's a whole different story.

Especially the last one is tricky. Even though I agree that in theory the cost of switching search engines is pretty close to zero, these habits die hard unless you have something to offer that is obviously much better.

So while Cuil and Powerset got a little bit of IT media attention, I don't think it is fair to say that they actually grabbed that much of Google's market share? And I'm not really sure it is that easy to make a new search engine that will be able to get the market share of ie. Yahoo!, Bing or Ask. Unless you can do most of the things mentioned above AND you have that extra special feature on top that makes everyone stop and stare. (Which then would have to be something the other search engines could not easily implement too and roll out within months :)

Disclaimer: I work for Yahoo!, but these opinions are mine alone.