Kerberos/RPC Authentication issue

There is one site with us which has 2 domain controllers and both DCs are GC an DNS. Every servers in this site point to these DCs for thier primary and secondary dns. The problem is that, we were doing security updates on both domain controllers. After the updates were finished we restarted them one at a time. Once the DC was offline then some of our servers started complaining about RPC, Authentication, Kerberos, etc. Every users that are connected to these servers loose their connection and have to re-authenticate. Event logs on the servers were failing about kerberos, RPC, etc. Below are some of the errors

Kerberos Event ID: 7
The kerberos subsystem encountered a PAC verification failure. This indicates that the PAC from the client username in realm DOMAIN.COM had a PAC which failed to verify or was modified. Contact your system administrator.

(It cant verify the user that is starting the service because it cant contact the domain/DC)

LSASRV Event ID: 40960
The Security System detected an authentication error for the server cifs/DC1.domain.com. The failure code from authentication protocol Kerberos was "The specified user does not exist. (0xc0000064)".

Well, it seems to me like there is a DNS problem or so.

This is an old thread I came across troubleshooting a similar issue, and thought I'd post what fixed my situation (I have probably 30-40 "Kerberos Event 7 PAC" issue links I've researched at least, none have this "fix"), so I thought I'd donate it here so it can be found on the web.

I tried all the tips I've found, adding/removing computer account from domain, DNS, using netdom, nltest, etc, nothing worked, the channel "looked" good, but nothing worked.

The common factors were Kerberos and Userenv failures, I noticed when I logged in with the local admin account, the logs were "clean", but either the domain admin, or user account, were not (but they DID let me login).

I finally decided to verify that the accounts were properly in the "local adminstration" security group to add/remove from the domain (although the domain was letting me do it, and the machine would show up in A/D (or disappear when removed), something was never "right". At first everything looked okay in the local "Administrators" group, but then I noticed that the <domain>\<username> was immediately followed by the SID (###-####...). The local admin user account was not displaying it's SID (as expected). At that point I knew I had something (this was 15 hours of work and research into the project on our COO's machine during off-hours).

So what happened, and how to fix it... at some point the machine lost it's Kerberos synch, as others have reported... then the user accounts tried to login to the domain (the user account, and then my domain admin account, trying to resolve the issue)... the accounts existed locally on the hard drive (cached), and had valid SIDS for the domain, AND the account credentials were still valid on the domain (SID never changed), which let the machine login to the network (but not establish Kerberos, or GPO, etc)... but the two were not really connected, but instead were just "passing" the SID back and forth without any real authentication. Essentially, the former "domain" accounts were now "machine local" cached domain accounts that could pass through A/D authentication as well, but they were not actually capable of authenticating the machine onto the network, and the netlogon was not capable of synching GPOs to the machine because the "domain" accounts were not actually on the machine any longer with Kerberos synch. Changing the machine domain membership was possible because it was popping up the authentication box (a clue I just now realized), instead of using the "local" machine accounts that were former A/D accounts.

Final Solution: As local administrator, remove all the "former domain" accounts from the system's local user groups (keep the profile directories though, don't remove the profiles), reboot and log back in.

Then remove the machine from the domain using the real domain account and reboot. Verified in A/D the machine was "gone". Then re-added the machine to the domain (which correctly added back the domain A/D account used for the join) and re-added the domain <user> account (which never actually changed in all this) back to the local admins group (I know, bad configuration, that's another battle for another day). Rebooted again to be safe, and logged in with the A/D <user> account.

The first time I logged in with the domain <user> account, I received an error and a temporary profile. I logged off, and back on with the domain admin account, which apparently "synched" up whatever was left to finish joining the machine (should have logged in with that account first). Rebooted and logged in again with the domain <user> account, and it found it's original profile (SID still matched at both ends), and is now working flawlessly.

So, if you lose Kerberos, remember to check the user group accounts on the machine, they also might have lost synch, and using "domain\<domain admin>" will LOOK like it is working, but in reality it is just the exact same name and SID as the "local copy" pseudo-domain/machine local" account as just described.
By NT design, this shouldn't be possible at all, a definite authentication flaw (probably really hard to reproduce, but if it happens to one person (us) it can happen again.)
There have been several Kerberos forum threads that appear to have gone unresolved, this might have been the final "key" to solve some of those, hopefully it will help someone else in the future. (I was at the rebuilding point when I finally noticed the SIDS that shouldn't have been visible, at 3:00AM)