it's not the server....... if some clients are logging in, its a client problem. Update all the clients to the latest patches, especially .net etc
when you say you tried it on a couple of clients... do you mean this isnt set up through a group policy? - that would definetly point to a client issue.
Her's a couple more ideas.....
Start, Run,
regsvr32 /s wuapi.dll
regsvr32 /s wups.dll
regsvr32 /s wuaueng.dll
regsvr32 /s wucltui.dll
regsvr32 /s msxml3.dll
net start wuauserv
wuauclt.exe /resetauthorization /detectnow
Or Try on one of the client boxes going to;
http://enter-wsus-server-name-here/ClientWebService/client.asmx
and see if you can get to that page.