Windows could not automatically update

I am having trouble with seemingly random computers regarding Windows Update. The computers at my organization are all set to update automatically as controlled by the system administrator. About half of the 60 computers update as they are supposed to. The other half give me Windows Update error 80072efd. These computers can get to the internet properly.

I have made sure that the websites are allowed through the firewall following these instructions: https://www.experts-exchange.com/questions/21634890/Sonicwall-blocking-windows-automatic-updates.html

All of the computers are connected to our main server which is running Windows Server 2008 R2. It is not OS specific - I have computers doing this running Vista, 7 and even other servers running 2008 R2.

The only way I am able to get the updates to come through is by removing the PC from the network and running them through the local admin. Once I do this the updates go through fine. I can then rejoin the PC.

Since I take the computer of the network and it works that tells me it's (probably) not the firewall or the A/V software since those are still on the PC. I am inclined to believe it's something with the server itself but I can't figure out what.

Any help would be appreciated.