Kerberos Error, Event ID 4 Server 2008 after Rebuild

A few months ago one of our 2008 Standard servers crashed.  We had a few corrupt file and ended up restoring the server using Backup Exec System Recovery.  During the restore we resized the partitions on the disk.  Afterwards we had some issues with AD and replication using DFS.  After spending hours on the phone with Microsoft, we resolved that issue by deleting some DFS files.  A few weeks ago, a user from that site (we have 4 AD sites) called and stated that outlook would not connect to Exchange (in a different site).  I did some research and found that we could not hit the exchange server, nor any server, by its hostname. I was getting the following error "Logon Failure: The target account name is incorrect".  After many hours of research I found the following article
https://www.experts-exchange.com/questions/21451056/W2K3-AD-DC-problem-event-4-kerberos-4000-4013-DNS.html
Which resolved the problem, or so I had thought.  The issue has resurfaced.

We have 4 AD sites, 3 of which have server 2003 sp2 + and the 4th has 2008 standard.  All sites are connected via vpn and we have ruled out connectivity.  

When I attempt to connect from site 4 (2008 box) to any other site via \\ netbios name or FQDN, I receive an error stating "Logon Failure: The target account name is incorrect".  If I connect to any other site using \\IP Address, the shares load up just fine.

The server is also loaded with System Event Source Security-Kerberos Event ID 4

The Kerberos client received a KRB_AP_ERR_MODIFIED error from the server server4$. The target name used was ldap/server4.domain.local/domain.local@DOMAIN.LOCAL. This indicates that the target server failed to decrypt the ticket provided by the client. This can occur when the target server principal name (SPN) is registered on an account other than the account the target service is using. Please ensure that the target SPN is registered on, and only registered on, the account used by the server. This error can also happen when the target service is using a different password for the target service account than what the Kerberos Key Distribution Center (KDC) has for the target service account. Please ensure that the service on the server and the KDC are both updated to use the current password. If the server name is not fully qualified, and the target domain (DOMAIN.LOCAL) is different from the client domain (DOMAIN.LOCAL), check if there are identically named server accounts in these two domains, or use the fully-qualified name to identify the server.

I have read a ton of articles and tried quite a bit with no success.

I have deleted and re-created the Replication Topology
Checked AD for duplicate computer accounts - negative
Reset the replication password for KCC
Rebooted the servers
Checked DNS for duplicate entries - negative
Ran the KCC connectivity tools with no errors