Remote Desktop Gateway - Certificate Revocation

We have a Remote Desktop Gateway server that users from the outside connect in on. All works well, except for a few random users. They get the error "Your remote desktop connection failed because the remote computer cannot be authenticated." "The remote computer could not be authenticated due to problems with its security certificate. It may be unsafe to proceed."

Certificate errors
"A revocation check could not be performed for the certificate."

I am outside the office now and am accessing the server remotely. No idea where to go here especially since it is only on random computers. This is a GoDaddy SAN certificate. I just purchased it.