I've had similar issues in our workstation and server environment (though it coincided more closely with the deployment of VSE 8.8 Patch 6 than with anything else). We ended up building the xDAT package into an EEDK deployment package and running it on the affected devices. It's resolved most of them at this point, not all.
What are you seeing in the Client Events?
Primarily, something along the lines of "update failed with unknown error". That's not the exact wording, but I'm not at work at the moment.
After deploying the xDAT package, most systems will accept the updated xDAT package, and will then update through the normal update process.
Do you have multiple agent handlers? If so, are the nodes having issue pointed at the same AH?
If you haven't already, bounce your agent handlers - if not possible, restart McAfee services.