I can confirm that with iinet and ADSL2+ I haven't encountered any issues yet, though, I man using a Laptop as a wireless bridge between the TiVo and my main network.

As Darren has asked, how is your TiVo connected to your network?
and an additional question I will ask is, what happens if you disconnect your TiVo from your network when the "slowness" occurs? does it speed up again?