Well, first and foremost, power-plug reboot. If you haven't don't this at least once (twice is usually better) since the software downloaded, that's probably your problem. I AM assuming we're talking about SATELLITE receordings - OTA is a whole different can of worms - lots of threads to read both here and at DBSTalk on that subject.
If the above does not help, try deleting ALL timers, and doing a power-plug reboot. I've found that that will fix corruption in the timer database, although I haven't had to do that for a couple of software releases now.