I recently replaced my Mitsubish WD52625 set with a Sammy HLR6178W. First impression was that the Sammy had 2 things majorly lacking -

1) The image had a high amount of digital distortion, very grainy.
2) There was a choppy feel to the video.

Is this something that's known, and are there any ways to help curb this?

i just replaced that tv with a 61a750 samsung. The samsung has way better color and the mistsu looked washed out. the samsung also looked sharper. Maybe you had edge enhancement on or your sitting too close to the tv.

If your Mitasubishi was a CRT technology TV designned for SD TV broadcastrs then it is only normal that by replacing it with a High Definition digital technology HDTV that your SD TV programs will by look worse since they are being upscaled which causes them to be grainy. Only HD resolution TV programs look better on a digital technology HDTV then they do on CRT technology.
What HDTV program source are you using with your new TV?