This article will only be useful if you are trying to use MSE on a business network with a Proxy server.

To cut a long story short, MSE is using different proxy settings from IE. This is according to How the Windows Update client determines which proxy server to use.  So, even if the logged in user is using a certain manually configured proxy, Windows Update is not and is trying to connect directly.  So the trick is to use proxycfg.exe.  I simply typed the following on the command line:

proxycfg -u

and, presto, all udpates went through!  The -u option copies the proxy settings from the currently logged in user.

proxcfg has gone missing in Windows Vista and Windows 7.  You should use netsh then.  The equivalent for the above is:

netsh winhttp import proxy ie
This should be run in a command windows run with administrator privileges. a reboot is not necessary.