The first place to look is in the agent log on the affected client machines (the actual log file rather than the status monitor.) Does it report any errors?
Post a zipped copy here if you like and we can have a look.
Are you sure they are getting the updates from the ePO server? They could be getting the DAT updates directly from McAfee.
Our mobile users are set to first try to update from ePO server, but when they are out of the office, the updates will be pulled directly from McAfee.
have you figured out what the problem was?
Du you have a backup of your EPO Server. When there is a problem with the certificates you have to import the keys from your backup.
Is there any enty in the server.log file where clients are not able to connect?