Kmelon and Seamonkey are 2 other Mozilla Based Browsers besides Firefox. Opera is another fine browser in its own right. I was just trying to see if you had the same problem using a different open source browser. As you should be able to tell. I don't run IE either, or even Windows. I also wonder why you can't uninstall Firefox and reinstall it either. Sounds like the 2 problems may be related maybe. You should be able to do this.
Have you thought doing a
Highjack this Log in case it is malware that is the root of this problem.
I don't run Windows so my expertise on what to advise you to do is limited because I run only Linux machines.