1) Install TiVo File Decoder
Download source from http://sourceforge.net/projects/tivodecode/files/ the 0.2pre4 version works fine for me. Extract the source and build it.
sudo make install
Use "which tivodecode" to make sure it was installed properly in /ur/local/bin
2) Install Mencoder
Enable Medibuntu https://help.ubuntu.com/community/Medibuntu
sudo apt-get install mencoder