Has it been overnight yet, or did it just get installed today? My searches didn't work at all yesterday, but they work today. Then, even though I get search results, if I hit 'select' on any of the results, my box just thinks about it. I'm assuming that will fix itself in another day too
Dish should (if it doesn't fix the software to make Search work on the first day) add "Search will work tomorrow" to their installer training materials.