You give us very little to go on there terry. What icons? The ones on your desktop? Start menu? Just your browser? Everywhere? What browser? What operating system? Is this a laptop or PC?
How did you clean out everything? With what?
You might check out the Microsoft PowerToy - TweakUI - it has a Repair Icon option that might work, depending on what icons are broken on your system.
Sorry about that, just went through getting rid of a malware.
So far it is just the icons associated with the interner browser (IE7) that have had issues.