I'm not sure how you have things connected but it sounds like the HDCP "handshake" is giving you problems. The "handshake" is negotiated every time a component (TiVo, TV, A/V receiver, etc.) is turned on. If the "handshake" is lost it can result in no picture or even copyright protection warning screens.pagefault said:
Best bet is to either try new HDMI cables or switch to component output from TiVo. Connecting component out from TiVo directly to your TV and digital/optical audio out from TiVo to your receiver should give you what you need and the PQ will be as good as HDMI. Here's a pretty good article about HDMI connections and some of the problems that arise.
Let us know how things go.