What version of windows we talking about?
I have seen your question in a couple forums so I will not bore you with the netsh commands because I'm sure you found and used those. Have you installed any software before this started?
Doing a search for this in google has alot of hits, so if I had to guess I would say some malware is doing this. And its fairly nasty because system restore or a complete format seems to best way to fix it. I know you said you scanned but I would go to this post
in these forums. I am not sure what you are using to scan but the steps in that post would be a good idea. If they say you are clean then post back here and we'll go from there.
Edited by CaveDweller2, 18 July 2009 - 04:21 AM.