If I understand correctly, you convert tivo files to Mp4s for your iPod, but the converted files won't play on the 360? I don't have a 360 so I'm not sure what codec it needs, but I do know that Tivo files have a 'wrapper' that prevents the files from being used by most editors.

I use a program called Direct Show Dump to 'unwrap' the Tivo file and make a regular mpeg that I can work with on any device. You might be able to use this procedure to transcode between the tivo file and a compatible 360 file.