I tried pyTivo as well and it seems to be working on all the videos I was having a problem on. Thanks for the suggestion, Attack! pyTivo does seem a tad slower, but that might be due to the quality settings I've made in the config file.

Now I just need to figure out why VideoReDo is suddenly giving me all sorts of errors when I'm dealing with .tivo files...