When you say... "the hard drive isn't full so that isn't the issue", not sure if that is totally correct. The spare space is managed with content you might be profiled for, such as Suggestions to watch etc, but should not cause outright slowness. I have to admit my TiVo is not only nosier with hard drive chatter these days, it seems to be much slower since a recent code drop.
I can only suggest, though, following the advice of the post above. Best of luck