Did you have 720p included and native on when you were having the problems? Was it certain programs/channels, or all of them that were 720p? HDMI or Component?
Just trying to isolate the problem... I briefly tried Native on and had 480p, 720p and 1080i selected... and I didn't notice much, if any, difference between the PQ of 720p and 1080i....