"System detected a possible attempt to compromise security" Enter network password popup comes up on 2008R2

I came across an odd issue recently where a system was getting this error whenever you tried to access network resources. Additionally domain connectivity was not working very well. Some symptoms included:

1) Dns registration failed (secure DDNS)
2) Group policy processing failed: Event 1053 "Could not resolve the user name"
3) LSASRV 40960 events with authentication errors to various kerberos services such as domain controllers LDAP/ SPNS, and cifs/ for the DFS namespace.
4) TerminalServices error 1067, Cannot registery TERMSRV Service Principal Name
5) When joining the domain and changing primary dns suffix "Changing the primary domain DNS name of this computer failed." "A Directory service error has occurred"
6) Klist shows no kerberos tickets

When I looked at this in netmon, all of the Kerberos transactions for TGT requests would receive a preauthentication required error from the KDC (domain controller) and it wasn't following up on that. After trying to dig around for information related to that, and any possible Kerberos settings that might impact this, I could find nothing. I looked in the registry for LSA settings and found LMCompatibilityLevel at 1. After changing this to a 2, everything started to work fine. From the Microsoft description of NT Compatibility levels, I don't see how this would impact Kerberos transactions, but apparently there may be some correlation. This fix worked for a short while, however everything broke again soon after. Later investigation found the Kerberos encryption types had been restricted to AES only, which was not compatible with the domain. After enabling RC4-HMAC, the problems went away. I have seen related issues on other machines where neither of these two should have been the problem. So perhaps there are many causes.