First, you can try using the Tivo kickstart tests
to check the hard drive on the Tivo itself.
How recently was the hard drive replaced? What model hard drive? Is it still under warranty?
If it is beyond warranty, then you can burn a bootable diagnostic CD from the hard drive manufacturer's website, pull the hard drive from the Tivo and hook it up to your computer, and then run the long test on it.
But before you do that, you might want to eyeball the power supply closely and check for capacitor plague
You can't rule out that it may just be a signal issue, or a glitch in the transmission itself. The Tivo only records what is input. GIGO.
How are you getting your TV programming? Cable, OTA, or ?
Something else comes to mind.
When you replaced the hard drive, did you DIY by copying the old to the new?
If so, are the glitches you're seeing only happening in the recordings that were copied over?