Did you try connecting the tv directly, then telling the tivo to "test", then connect through the receiver and have it cycle through the different resolutions, to see which ones will work and which ones wont?
Did you try a different input on the receiver?
Did you try a different HDMI cables?
both between the tivo and the receiver as well as between the receiver and tv... if the tv's been moving, the cable might have received a little wear n tear)
Does that receiver do any sort of signal processing?
If so, does it have a "direct" mode or such that takes the processing out of the loop, or try toggling the available options.
Does the tv have any features in the area of video quality in regards to HDMI signaling?
e.g. Deep color, extended blacks, etc
Have you tried toggling any HDMI extra functionality such as CEC, Power Control or ARC as available on the Receiver and/or TV?
-Roamio Pro/Slide Pro
-Stream (Gotta go unplug the sucker one of these days!)