I have well over 700 recorded TV programs. Contrary to the other posts, the problem is almost certainly not your hard drive or the fragmentation of it or extra files on it.
I have 4 SATA 7200 drives, 1 for the O/S, one for paging/swap, one for my data and one for the TV progs, which is a new and v fast Hitachi 1TB drive.
The problem is that MCE re-builds it's index every time you list your recorded shows and, even worse, everytime you come back to the list from viewing one particular show's details. Any idiot programmer can write software that will kill even the fastest hardware if they want to or are too lazy to think about it. Why Microsoft still employ them I don't know, how difficult would it be to write the index once to a file only when it changes and then just read the file?
In the recordings listing try changing from 'view by date' to 'view by title' - it is instant even with 700 shows! However if I go out and come back in it takes me 24 long seconds to re-build the index. What did Micrtosoft think people were going to do with a TV recorder, just record 10 programs?