Just came across this error when running Windows Update on a fresh install of Server 2008 R2. Not a good start!
Initial suggestions pointed to the system date/time which was indeed incorrect, however after fixing (and even rebooting just in case) the error still appeared?
Turns out you need to update the root certificate for the machine first! You can download the update for this from the following Microsoft URL:
http://www.microsoft.com/download/en/details.aspx?displaylang=en&id=5397
Once downloaded, double click on the file to install. There’s no feedback to say it’s run successfully, but Windows Update suddenly springs back into life..
Now downloading the first 30 updates of many probably!…
Microsoft has pulled this update. You wouldn’t happen to still have the downloaded update file, would you?