After taking a look at that error message it looks like it is a wsus error. Are you running Wsus? This error can be caused by either a permissions error or a problem with your internet/proxy/firewall setup.
Have you had Updates/WSUS running properly before? Is this a first setup?
This Microsoft KB article talks about the possible issues with your internet connection or proxy setup:
And this article from Microsoft talks about how permissions can cause this error
Let me know if either of these fix your problem. If not can you post some findings from the error logs on the affected machines and list service packs installed and what else does this server do.
Are all machines in your network affected by this or just this one server? Can it connect to the internet? Is it pulling updates from the internet?