Give this a try, go here: http://www.microsoft.com/genuine/
and validate your copy of Windows, if you are told that your copy of Windows is valid, then go here:
http://support.microsoft.com/ph/1173 and tell them the problem you are having installing the first Service Pack. Notice these options: Need More Help?
Contact a Support Professional by Email, Online, or Phone.
If you have a valid copy of Windows on the computer they will help you. Make sure you tell them you have malware issues and once the first Service Pack is installed, you will receive help removing the malware, and will install Service Pack #2 when that has been done.
When you have that first Service Pack installed, follow the directions I posted earlier, return to your topic and post a HJT log reflecting that installation and I will be glad to continue the cleanup.
Thanks