Thansk for the comments, let me clarify a bit.
Its an HP z545 with a 3Ghz processor, 1.5GB RAM and a single 400GB drive running Vista RTM. It may well be the drive, but everything else seems to work fine. I'd think if I was having trouble with it, it would show up as bad video play and that sort of thing, rather just just being slow to display the recorded show guide. The regular channel listing guide displays just fine.
The OS is on the same drive and partition as the shows. There is currently no AV software and yes I have defragmented and done other basic tune up procedures. All in all it runs fine, just that one set of menu's is slow.