Hmmm, since it just started with adding the HDMI, two things come to mind right away as WAGs:
1. The HDMI cable is "too long" and reflecting back somehow.
2. One of the outputs is set for interlace, like Video > Progressive Scan is ON or OFF and you're sending the opposite scan thru the HDMI, like 1080i, or vice versa. Make sure both are sending Progressive?
On reflection, here's a snippet from a Blue Jeans Cable piece on HDMI and run length:
"The best twisted pair cables control impedance to about +/- 10%. When a digital signal is run through a cable, the edges of the bits (represented by sudden transitions in voltage) round off, and the rounding increases dramatically with distance. Meanwhile, poor control over impedance results in signal reflections--portions of the signal bounce off of the display end of the line, propagate back down the cable, and return, interfering with later information in the same bitstream. At some point, the data become unrecoverable, and with no error correction available, there's no way to restore the lost information."