Have you tried seeing if this happens with all video inputs or just the TIVO? For example, is this happening with your DVD player as well? This would help you figure out if it is the TV or the TIVO.

If it is happening only with the TIVO, you might try seeing if it is happneing with all outputs of the TIVO (coax, RCA, s-video) or just with the outputs you currently have hooked up.

Hope that this helps.