Might want to check your hosts file, and see if it set up a proxy in Internet options. Other than that, it depends on what virus/malware it is that caused it. Sometimes you can find specific instructions on cleaning it out. Usually if it's that persistent it's just better for a clean install though.