Have a look in the Software section of this forum for the thread about Spyware removal. What you may need to do is run WinsockFix or LSPFix to remove the bit of spyware that's inserted itself somewhere in your TCP/IP stack (read: between the Internet and Windows). When you remove spyware, occasionally it leaves pieces behind that it can't remove.
Removing the offending part using LSPFix should fix the problem; believe you me, I've seen this a lot at work and it's highly frustrating. If you need more help, post here what LSPFix is saying is in your stack, and I'll try and help you identify the erroneous bit.