Before formatting the DVR, I would recommend double checking the jack. Connect a different STB to it and see if live TV is pixelating on the same channels as on the DVR.
Since you said it's pixelating on both live TV and recorded, I would lean more towards interference on the line.. if the DVR is recording pixelation then it will always play back pixelation, regardless of the location of the DVR.
Here are the instructions to format the DVR HD (this will erase _all_ recordings and schedules):
1. Access the diagnostics menu
2. Within 5 seconds, pressed Replay, DVR, DVR, DVR, FiOS TV on the remote (Replay is the curled arrow pointing left)
3. After a button press the STB front display should read "Clr" . Exit and the STB will reboot, clearing the hard drive