I looked on Google - there is a lot on there about it. It looks as if there are several different potential causes of what you have, with a different cure for each.
The probability is that in removing the nasties, something has been damaged or deleted that IE needs to run. A suggestion that looked like my way of fixing things was this:
Try a repair on Internet
Explorer in the Add-Remove programs applet, Windows Installation, by double-clicking
on the entry "Microsoft Internet Explorer and internet tools" and choosing Repair.
If that doesn't do it, are you running the Microsoft Firewall? I found that does strange things, and turned it off in favour of using ZoneAlarm.