Alyson Shontell cites a moment of candor from Zuck:

During an interview with Bloomberg BusinessWeeks' Brad Stone, Zuckerberg said it was "generous" to suggest that Graph Search worked even half the time. 

From Bloomberg BusinessWeek:

When it’s suggested that Graph Search works about half the time, Zuckerberg says that’s being generous. Vernal, the engineering vice president, says Graph Search was the last major product designed primarily for desktop computers. It’s now being redesigned for phones. He cites the opportunity to use a user’s location to deliver results relevant to where they are. If a user is traveling in New Zealand, for example, Facebook should serve up previous updates and insights from Facebook members who have visited Auckland. Vernal says harvesting all this data, amid some trillion status updates posted throughout Facebook’s history, is “a multiyear journey.”

A trillion status updates = SO WOW

Also, clearly Zuck is evolving. Search based on location is much more useful than search based on social, and even he now admits it. 

Another note: This is the first quarter Facebook had over 50% of its revenue from mobile. 

Repeat: 53% of their $2.5 billion in revenue this quarter is from mobile. 

So from now on Facebook is mobile first. Mobile over desktop. Mobile over even social. 

Watch Facebook ship mobile apps this year that can be used without Facebook connect. 

But it had so much potential....

http://pandawhale.com/post/14707/introducing-graph-search-facebook

http://pandawhale.com/post/15019/actual-facebook-graph-searches-current-employees-of-tesco-who-like-horses

http://xent.com/pipermail/fork/Week-of-Mon-20130121/062457.html

Makes me wonder where they went wrong. The idea or the execution?

It's disabled for me and has been for a while now -- I am unable to search my or friends' status updates.

Well that would suggest that it's the execution that failed.