I recently installed Windows Server 2008 R2 64bit direct from an ISO and when I went to update with Windows update, it fails with Error Code 80072F8F . WTF? It's 'brand new out of the box'. Well, that's the tip off. Many web hits will tell you to check your date and time. But 99% of the time, that's synchronized anyway. But the root cause is actually the same... certificate failure. What you need to fix the problem is the root certificate list must be updated. Microsoft releases updates to this frequently via Windows Update, but you have a chicken and the egg syndrome. You must manually download the update and install it before Windows Update will run.
'But update root certificates doesn't apply to Win2008!' you say. True, when the system is working. Win2008 automatically updates these from Microsoft while XP required manual updates. But it appears the default certs in the ISO aren't good enough to even connect to Microsoft anymore, so they must be manually updated before the Automatic Processes can take over.
Goto http://technet.microsoft.com and search for 'root certificate update', find the latest (even ones from 2009 seemed to do the trick and download. It will be an .exe that when double clicked seems to do nothing.. but don't worry. Once you've ran the file, run Windows update again and all is good!