I wish Jakob Nielsen would have provide some more details on this part of his latest article:

<<If you thought it's easy to get to Google, think again. In our current round of usability research, only 76% of users who expressed a desire to run a Google search were successful. In other words, 1/4 of users who wanted to use Google couldn't do so. (Instead, they either completely failed to get to any search engine or ended up running their query on a different search engine — usually whatever type-in field happened to be at hand.)>>
http://www.useit.com/alertbox/designer-user-differences.html

I don't understand. The task was to search on the web or to access Google's homepage? If they used any popular search engine at least once, finding Google would've been a piece of cake. Or maybe they were tricked by Yahoo?
http://search.yahoo.com/search?p=google&ei=UTF-8&fr=moz2

Note that Nielsen says, "Instead, they [the users] either completely failed to get to any search engine or ended up running their query on a different search engine — usually whatever type-in field happened to be at hand."
So I think he does not refer to people who start out as Yahoo, but perhaps people who stare at their Windows desktop looking for "that blue e" or their blank browser homepage.

Plus, as Nielsen says, "for this round of research we're deliberately recruiting above-average users, so the success rate across all Internet users is probably lower than our finding."