That sucks. If all else fails, you can try removing IE through add/remove programs. Go to Add/Remove windows components and reinstall. Worked for once

You may or may not loose your bookmarks

Try at your own risk and good luck. Another spyware removal program you may consider first, spybot,
http://beam.to/spybotsd It's free and works well.