This happened again to me yesterday, so I tried the format button, and it did appear to fix it, but in reality it didn't, because I was then at 480p resolution again. The only way for me to fix it was to go into the HDTV setup, change the resolution to 480p (I know, it said 1080i, but the resolution looked horrible) and then change it back to 1080i.
This is an insane thing to have to deal with on a regular basis. Come on DISH!!!!
Same thing happened to me yesterday on the 722 and I did the same thing you did. That seemed to fixed it but this is the first time I see it happen and I hope it doesn't happen again.