You must use Internet Explorer to access Microsoft and Windows Updates.
First of all, open IE and make sure legitimate Active X settings are allowed and the security level is set to "Default" which should be medium.
Put Windows Uodates in your "Trusted Zone".
Next - go to the Windows Update site and set it to download and install updates automatically. That should enable critical updates even if there is a problem with the "Genuine" test.
How did they install your XP op system on the new hdd?
Did they use your Windows XP Installation cd or did they image the drive?
If you continue to have problems updating:
Microsoft Security Product Support Policy
Technical support is available from Microsoft Product Support
Services at 1-866-PC SAFETY (1-866-727-2338). There is no charge for support calls associated with security updates.
International customers can get support from their local Microsoft
subsidiaries. Phone numbers for international support can be found