So we have two TiVo's and oddly enough the newer of the two has given us fits off an on for a while now. I believe the issue is related to the hard drive. It is either badly fragmented and the built-in cleanup routines are not completing -OR- the drive itself has some bad sectors or other physical defect.
So after doing a little research, I have found the basic steps required to replace the hard drive. Looking at a web based company that specializes in selling replacement drives, I was able to determine that a Western Digital AV-GP drive would be a good replacement. I ordered a 1TB drive to replace the factory drive last night. It should be in, in a few weeks, as I opted for free shipping. I am planning to document my TiVo upgrade process on my blog here, for both my own log of it as well as to share with other TiVo fans that are not afraid to get their hands dirty.
Consider I have built, broken down and rebuilt dozens of PCs, I don't think it will be too complicated.