Domain controller cannot find the domain?

Okay, so I'm having an intermittent problem (which is always the best kind) and its starting to become a real pain.

Not too long ago we had a simple Active Directory network. Server A was the main domain control and server B was a backup domain controller. Then server B died. Now we have a new server which is hosted in the cloud by Amazon Web Services: server C. Server C was connected to server A over a site-to-site VPN, joined to the domain and added as a domain controller to replace server B.

After about a month or two we started to run into this problem: when someone tries to log on to server C they get this message: "The specified domain either does not exist or could not be contacted". The only thing they can do is click "OK" which closes the Remote Desktop window. To me this makes no sense because server C is a domain controller so it should not have to look any further than itself in order to "find the domain" and log the user in.

Anyway, the server will continue to show this message to any user who tries to log on. Users who are already in are unaffected. Rebooting server(s) C and/or A will sometimes fix it, but not always. After a few minutes/hours the server will start letting people in again and will work fine for a few days.

After it lets you log in again, a message is displayed saying that the server could not contact the Remote Desktop Licencing Server and that the licence will expire in xx days. This message goes away by itself and when you look at the settings it seems to have no problem finding the licencing server, which is server A.

Looking at the event logs on server C, I find:

Automatic certificate enrollment for [DOMAIN]\[USER] failed (0x8007003a) The specified server cannot perform the requested operation.

All servers are running Windows Server 2008 R2 and are accessed using Remote Desktop Connection.

Can someone please tell me what is going on and maybe even how to fix it?