Can't you still get MSN TV up there? Most cable providers now have a DVR option - I have mine through Charter Communications.
You could put a TV tuner card in your computer, like ATI's All-In-Wonder, which comes with DVR-like functionality. These are getting cheaper by the minute and is essentially free after the initial investment.
If you're up for a mini-project, and are fairly comfortable with linux, you could build your own using
MythTV.
HTH