Hi,
Check this article
Test SEP to GUP and GUP to SEPM communication
http://www.symantec.com/docs/TECH153328
Symantec Endpoint Protection: Troubleshooting Client/Server Connectivity
http://www.symantec.com/docs/TECH105894
Also if these articles are not helpful then pass on Sylink debug logs from 1 or 2 affected clients.
The only way to know what is really going on during the communication process is to enable Sylink debugging on a client that is not updating, allow debug logging to run for 10-15 minutes, then disable again. If you like you can attach the log to the thread for review.
How to enable Sylink Debugging for Symantec Endpoint Protection in the registry
http://www.symantec.com/docs/TECH104758
And ..
Here are few Troubleshooting Articles you have have to look at:
Symantec Endpoint Protection: Troubleshooting Client/Server Connectivity
http://www.symantec.com/docs/TECH105894
Symantec Endpoint Protection: LiveUpdate Troubleshooting Flowchart
http://www.symantec.com/docs/TECH95790