This isn't line noise. I have seen this problem in the TiVo systems by DirecTV. What type of video cables are you using? You should try composite cables if you are using S-video. I have found the S-video outputs to cause a grainy picture. Also, in your tv picture setup, you may have a video DNR setting. If so, turn it off. The video distortion I have seen from the tivo by DirecTV looks like heats waves around the images. Some tv's like the new RCA's may look better using the RF cable. While other's look better with the above mentioned composite. But, none have looked better using the S-video.
It takes 2 to tango, but only one to be nice!, A/V Slave