I think the first thing I would do is check speed/duplex on all the ports from the tivo to the router, inclusive. If you're unable to check them, try (temporarily) swapping connections to different switches.

You might also check for errors on those ports, if possible.