What's wrong with web search today?
It's easier for me to point to what web search should be and then highlight the differences. If web search were perfect, then it would produce an answer to every query that would be as good -- or better -- than if the smartest people in the world had as much time, data, and contextual information (about the user) required to fulfill the query; and it would do all of this in a split second. In other words, the search engine would be an artificial intelligence (AI) so smart that if a correct answer could be found in theory with close to infinite resources, then it would find it. If a correct answer did not exist, then the search engine would give you the next best thing: an approximation, or perhaps even an explanation as to why your query has no perfect result. (And by the way, if we realized all of the above within my lifetime, I would consider myself lucky. That should give you an idea of what sort of time frame I am talking about.)
Alternative interfaces, like cell phones, voice, and snazzy graphical results are all nice, but in the end they represent relatively easy technology problems when compared to the challenges involved in realizing our hypothetical search engine. What really matters is what is under the hood.
Today, search engines have almost no understanding of words or language in any significant way. They exploit the statistical properties of words and links, but in no way is there anything going on akin to understanding. Search engines don't recognize user intent, can't distinguish goal-oriented search from browsing search, and are completely ignorant of the subtleties of how different concepts relate to one another. Moreover, they completely lack wisdom -- i.e., they are very poor at distinguishing between trivia and something profound.