I upgraded my Toshiba Tecra A11 laptop from Windows 7 to Windows 8 and I'm getting this error message. I've used the troubleshooting wizard to no avail. I've also checked my broadband connection and no problems there.
I ran into this on two machines. On one it fixed itself after a day or so (which gave me the clue as to the solution that worked for me on the other) and for the other it was obviously caused by a particular old MS application I use, and after some messing around getting nowhere with the MS trouble-shooters and uninstalling and reinstalling the trouble causing application (uninstalling it fixed the Update problem, reinstalling put the problem back) I instead fixed it by temporarily changing my connection's DNS server addresses to preferred public ones.
For example, go to Control Panel>Network and Internet>Network Connections and right click on the connection you are using and select Properties. On the General tab scroll down to Internet Protocol Version 4 (TCP/IPv4) and select Properties.
Select Use the Following DNS Server Addresses and enter 126.96.36.199 for Preferred DNS Server and 188.8.131.52 for the Alternative.
Try Windows Update - if it works you will likely find that after updating you can change the DNS servers back to being obtained automatically and Update will be fine thereafter.