Yet something newer than the below, the Windows Update Automated Troubleshooter:

https://support.microsoft.com/en-us/gp/windows-update-issues/en-us

Microsoft is now providing an interesting toolset for Windows Update issues on current operating systems:

http://support.microsoft.com/common/survey.aspx?scid=sw;en;3779&showpage=1

And another Fix-It:

http://support.microsoft.com/kb/968002

And something to install, the SDK, which contains Windows Installer 4.5 and possibly 5.0 too:

http://www.microsoft.com/downloads/en/details.aspx?FamilyID=c17ba869-9671-4330-a63e-1fd44e0e2505&displaylang=en

The below are our previous methods, from the indefatigable Mike Hunsinger. It is best to try level 1, see if that fixes, go to level 2. Both of these are done in administrative command prompts.

Level 1.

1. Stop services:
   net stop bits
net stop wuauserv
net stop appidsvc
net stop cryptsvc
2. Rename folders:
   ren %systemroot%\SoftwareDistribution SoftwareDistribution.bak
ren %systemroot%\system32\catroot2 catroot2.bak
3. Start services:
   net start bits
net start wuauserv
net start appidsvc
net start cryptsvc
4. If in Windows Vista or Server 2008 R1: bitsadmin /reset /allusers

Level 2.

1. Stop services:
   net stop bits
net stop wuauserv
net stop appidsvc
net stop cryptsvc
2. Deletions:
   Del "%ALLUSERSPROFILE%\Application Data\Microsoft\Network\Downloader\qmgr*.dat"
3. Registrations:
   cd /d %windir%\system32
regsvr32.exe atl.dll
regsvr32.exe urlmon.dll
regsvr32.exe mshtml.dll
regsvr32.exe shdocvw.dll
regsvr32.exe browseui.dll
regsvr32.exe jscript.dll
regsvr32.exe vbscript.dll
regsvr32.exe scrrun.dll
regsvr32.exe msxml.dll
regsvr32.exe msxml3.dll
regsvr32.exe msxml6.dll
regsvr32.exe actxprxy.dll
regsvr32.exe softpub.dll
regsvr32.exe wintrust.dll
regsvr32.exe dssenh.dll
regsvr32.exe rsaenh.dll
regsvr32.exe gpkcsp.dll
regsvr32.exe sccbase.dll
regsvr32.exe slbcsp.dll
regsvr32.exe cryptdlg.dll
regsvr32.exe oleaut32.dll
regsvr32.exe ole32.dll
regsvr32.exe shell32.dll
regsvr32.exe initpki.dll
regsvr32.exe wuapi.dll
regsvr32.exe wuaueng.dll
regsvr32.exe wuaueng1.dll
regsvr32.exe wucltui.dll
regsvr32.exe wups.dll
regsvr32.exe wups2.dll
regsvr32.exe wuweb.dll
regsvr32.exe qmgr.dll
regsvr32.exe qmgrprxy.dll
regsvr32.exe wucltux.dll
regsvr32.exe muweb.dll
regsvr32.exe wuwebv.dll
4. Reset networking:
   netsh winsock reset
5. Reconfigure proxy settings:
• If on XP: proxycfg.exe -d
• If not on XP: netsh winhttp reset proxy

6. Start services:
   net start bits
net start wuauserv
net start appidsvc
net start cryptsvc
7. If in Windows Vista: bitsadmin /reset /allusers
8. Install the latest Windows Update Agent.
9. Reboot.