Thats a nasty Downloader variant virus. Its classed as adaware.
You have by the looks of it tried to remove the offending application and it now is showing the message.
Erm, I think there is a tool for removing the entires related to it.
But as a measure the only way to do it is reinstate the spyware by recovering the files from adaware or spybot.
THEN... uninstall the spyware via tools > internet optioons > downloaded program files > right click on the offending component and remove.