Run the symhelp tool on one affected client to see what errors come up:
Troubleshooting computer issues with the Symantec Help support tool
http://www.symantec.com/docs/HOWTO80839
Have any changes been made to the GUP policy-wise? Sounds like clients are not grabbing the defs from them.
You can also enable sylink logging on one client to see the communication.