Its funny you say the answer is "Search" but of the 4 things you want to do when you fire up your tv, none of them are "Do a text based search for content".
1. Go to specific channel
2. Find if a program is playing right now
3. Browse a category of programs
4. Access an existing digital library.
Existing remotes actually do many of these pretty well. A keyboard based search only really helps with 2 and 4 and even then might actually be an ancillary experience unless you are looking for something specific. Text search only helps when you are looking for specific content it helps you find content you know exists. But I really don't think thats the main problem for people watching TV.
I think most people do what I do when I get home, sit down and try to find something interesting and new to watch. I think the problem is that most people have a hard time finding that cool new show or video. Now similar to the web, when I want to try to find something interesting I don't go to Google. I go to reddit or HN or fark or digg or some other source of curated content.