Presume you are running windows and Internet Explorer (IE). I've recently been hit by such malware (AV Security Suite). This shoudn't be the case since you reloaded your OS, but open you IE and look for a tab like "tools" in IE8, and "connections" there, and "LAN settings" under that. Look for a check box that's for "use a proxy server". Uncheck that if checked.
THAT is how these things hijack your IE ... by using this setting for a proxy server, THEY become your "server".
If you have reloaded your OS and this box is checked, the malware may still be around somewhere, somehow.
I had success booting in the safe mode (turn on computer, tap <F8> key for several seconds). That stopped the malware from working.
Then (after waiting a while to load, perhaps) when you get your Safe Mode version of the OS, sign in as administrator. Then open IE (should work in safe mode), download Spybot Search and Destroy
Run it. Select "Fix (all) problems". Then reboot when done.
If you then open IE and no connection, go do the unchecking of the proxy server box. Spybot doesn't do that (I wrote to them but don't know if they can fix that).
I don't know if the safe mode "dodge" will work for all malware, though.