For whatever reason (and there are about as many postulations as there are proven facts) HDMI connections are just "touchy" that way; they're basically a chain and occasionally one device will cause a blip that another device interprets wrongly.
Another issue can be the HDMI cables themselves. Many are directional, they have arrows indicating the signal directions. Others aren't. Some are $xx, others are $x. You'll see as many opinions as there are cable mfg about what makes a "good" cable. We went through a set of Vizio cables from a big box store that we just couldn't seem to get a stable result from and ended up getting another Monoprice set that have been working perfectly.
As a general rule I turn on the AVR first, then the TV. As you say the Tivo is always on, but in our case the TV (Sony Bravia NX810) always goes through a little routine of "checking for external speakers" so I always try to turn the AVR first so that the speakers are found.
Another aspect may be the order of connection between your devices; in our case we have cable connection going to the Tivo, then Tivo to AVR, then AVR to TV. That way we can listen to the radio channels when the TV is off. Our other Tivo is quite different setup, no AVR but instead a Zvox speaker.
If you also use your AVR with other devices (e.g. a CD player) then it could be that when you switch inputs there's some sort of an HDMI handshake that blows away the connection to the Tivo's signal.
On the AVS forums there was a long thread a couple of years ago about HDMI audio dropout problems and the most reliable way to solve it turned out to be getting a Monoprice HDMI splitter, which basically "fooled" the AVR into not getting the problem signals that blew away the audio to another device. Here's a long thread reference:
Originally Posted by CIP54
any idea why it could work for a while then stop working?
when I checked out the above link, the order of turning on devices seems to matter, but the tivo is always on, so can't really deal with that one!