I have had a problem over the last few weeks which started off with AUPD.exe popping up frequently on PC. Since that point I have had an issue with laptop running very slowly, Skype disconnecting without warning etc.
The PC has now been given a clean bill of health by the malware team (link below) but is still going v slow. I have also done the basics ie stopping programmes in startup, remove unwanted software etc.
As a last throw of the dice I wondered whether you had any other good ideas or whether this now means a reinstall.