TiVo still sees them as "format Purchased AAC audio file not mp3 or convertible to mp3." Luckily, The Apple Blog has a workaround. Simply convert your iTunes Plus tracks to either AAC or Mp3, and the file type in iTunes will be changed to "AAC audio file" or "MPEG audio file" respectively. TiVo likes that.
Yes, this will result in quality loss, but my television speakers hardly do the music justice in the first place, so who cares?