Spy Bot may also zap some registry files that might screw up your internet connection, so be ready to do a restore if that happens. Then pick and chose what to zap on each run until you can tweak it out...
I ran into this problem this past weekend. It jacked my connection all up. The computer wouldn't recognize my modem or anything. I hadn't done a clean install of XP in about a year and a half, so I went ahead and reinstalled. It's amazing how fast this computer runs now. :)