UPDATE: Good news! Some smart people have gone to the trouble of working out what to do with the timestamps in the tivo stream, and have written software to convert a tivo stream directly to an mpeg system stream using these timestamps for synchronization!
TyConvert: This is the original goods. It's a windows program with a fancy gui. Unfortantely, I had some trouble using it (memory allocation errors: it uses a lot of memcpy calls), probably because it is hard coded for "best quality" streams. I don't have a compiler for windows, so I didn't try recompliling it yet.
tyc: This is a hacked version if TyConvert, designed to run in a pipe under linux. I haven't played around with it yet, but I've put it up here because the links I've found to it were all dead. I'm hype to try it out, it looks like it's exactly what I've been looking for.
Other cools stuff: There is a cool TivoWeb project that has a pretty spiffy interface to your tivo and it's mfs database. In particular, you can do things like change the encoding bitrate and resolution that the tivo uses (see this bbs thread for an example of this). You can check out what the web interface looks like at this spiffy TivoWeb page. Unfortunately, it only runs on 2.0+. I may have to plug my tivo back into the phone line...
parse_stream.c: A program that writes the binary contents of a mpeg stream to stdout in a human readable way, and puts in line breaks before the mpeg start codes.
ConvertStream, version 0.1: A program designed to convert a TiVo version 1.3.0 tyStream into an mpeg2 audio stream and an mpeg2 video stream. The output streams can the be mulitplexed back together using mplex. (mplex is part of the mjpegtools package.) The resulting mpeg-2 system stream can be played on any mpeg2 complient player, such as mplayer.
I wrote this because ExtractStream wouldn't split the tyStream properly on my tivo, and the output from PlayStream on my TiVo was too corrupted to multiplex properly using mplex. I did find that ExtractStream was able to extract the raw tyStream itself with no errors.
There are some verbose instructions in the comments of the source code.
ExtractStream, version 0.2