This might not be an option for everyone, but I have my TV hooked up to an old Dell computer that I wasn't really using much anymore.
I then bought a USB Tuner for about 40 bucks so I could hook the computer up to a digital antenna (here's the one I'm using, which works great:
[Link: tigerdirect.ca]).
Using Windows Media Centre (usually pre-installed on Windows computers, but easily downloadable if it isn't), I get an automatically updated channel guide, and a perfectly functioning DVR, which saves my recordings to the computer's hard drive. It's fantastic, and for me, it was cheaper than buying a OTA DVR, although you need to have a computer you'd be willing to dedicate to your TV.