It really does sound like their is something flaky about your network or internet connection. Changing ISPs won't make any difference since you will still be using the same line, modem, and DSLAM at the other end. If you upgraded your modem though you might get a more stable connection. Have you got filters fitted to your phones?
Can you get any connection stats from your modem?
If your TiVo has had a PAL tuner fitted, and you have it plugged into an aerial, it could be that the RF output channel is clashing with a broadcast channel, and causing network problems.
Do some internet tests to see if they show up packet loss. On your PC you could try ping -n 100 oztivo.net and see what you get. Should be about 95%-100%