I'd start by running the Connection Tester from your main server to one of the pc's showing the symptom. Look particularly for the ability to access the admin share C$ and if it can manage a scheduled task.
The end of the connection log should read as follows:
Checking C$ Access
Deployment Folder: OK
Access Rights: OK
Checking Task Scheduler
Task was successfully scheduled
Task ran successfully
Task Deleted
Done.