KB ID 0000585
Problem
Seen on a “Brand New” Install of Windows Server 2008 R2, while attempting to install the Windows Server Update Service.
Windows Server Update Services Installation Failed The update could not be found. There may be a network connection issue.
Solution
1. Internet access was fine, though as it was complaining about an update, I did a full Windows update, and left it running while I went for a coffee.
2. Post update, the installation proceeds without error.
Update 24/05/16
Email From Efre: I had the same problem with WSUS, and the problem was that I was trying to install a new fresh WSUS, having had a previous installation that was out of service. But I had not removed the domain update policies from Active Directory. The new WSUS install reports the same error that you show in your post. Thanks to you I realised that.
I hope this helps some else.
Regards
Related Articles, References, Credits, or External Links
Windows Server Update Services – Install and Configure (2008 R2)