Some Windows 7 machines stopped updating. Trying to run Windows Update manually returned following error:

Windows could not search for new updates.
An error occurred while checking for new updates for your computer
Error(s) found: Code 800B0001
Windows Update encouraged an unknown error

This only affected updates from WSUS server. Checking updates directly from Microsoft Update worked fine.

Issue was resolved by installing Windows Server Update Services 3.0 SP2 patch KB2720211.

07.2012
Windows Server Update Services 3.0 SP2
Windows 7