Scan your system throughly before taking different actions... What antivirus you've got? Change either to nod32 or AVG.
Run different types of antyspyware programs, they should help.
Also clean your history and cookies if this message appears only if you open internet.