I would first try running IE setup and do a repair of the installation. Are you currently running any antivirus software such as Norton or McAffee? Do a full virusscan. It's also a good idea to pick yourself up a trojan scanner somewhere. I'm sure someone else around here could recommend a good one (since I don't know).
I would run CWShredder first in this case, but you should also read my Malware article, linked below. At some point, download and run HijackThis. Note: read the instructions on the linked page very carefully (the main download link is broken -- use one of the mirrors). Do not actually remove anything from your startup or Registry until you have posted the log that it generates and are given explicit instructions on what to remove.