Having the same issue. For example, with the cursor highlighted on a program in the EPG, press Search, Search doesn't even return that very program as a result, not to mention any further instances on that program clearly in the EPG.
Was just installed yesterday. In general, no matter what type of search, "No Results" is all I'm getting.
On a side note, also not getting any "Cover Art" on any DVR, or EHD recordings, but do seem to have access to the Internet (Weather Channel App works) and Broadband screen show's three green "OKs".