Active Directory replication fails with Event 2042 reporting “It has been too long since this machine last replicated” and replication status 8614: “The Active Directory cannot replicate with this server because the time since the last replication with this server has exceeded the tombstone lifetime.” and

Time of last successful replication:

2000-11-19 14:09:12

I got this error on a site with 3 DC’s and yes that puts you 12 years back, even before this company existed.
Normal solution would be demote and promote the problem DC, but, after looking around technet I bumped into this article : http://blogs.technet.com/b/askpfeplat/archive/2012/11/19/did-your-active-directory-domain-time-just-jump-to-the-year-2000.aspx and an updated article http://blogs.technet.com/b/askpfeplat/archive/2012/11/23/fixing-when-your-domain-traveled-back-in-time-the-great-system-time-rollback-to-the-year-2000.aspx, well that explains it all. the main PDC NTP was pointing at USNO.NAVY.MIL and on November 19th, 2012, time servers at USNO.NAVY.MIL incorrectly provided time samples listing CY 2000 as the current year between the hours of 21:07 UTC and 21:59 UTC (16:07-16:59 EST).

-Run W32tm /stripchart /computer:NTPServerAddress to make sure you are getting the correct time from your new source.

-Set the correct time settings to a known good source.

1. Locate and then click the following registry subkey:HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\W32Time\Parameters
2. In the pane on the right, right-click NtpServer, and then click Modify.
3. In Edit Value, type Peers in the Value data box, and then click OK.

-Run w32tm /config /update

NOw ofcourse you are having replication issues as AD replication would have happened when the time was set to the year 2000 and when your time is back from the past you are bound to have replication issues due to tombstone settings.
Proceed with making sure “Strict Replication Consistency” is enable in the registry value(HKLM\System\CurrentControlSet\Services\NTDS\Parameters\Strict Replication Consistency ) has been set to the default for Server 2003 and greater value, which is 0x1 before you do.“Strict Replication Consistency” will ensure that no lingering objects will be replicated out if they really exist after we force the replication to happen.

Note: This forces the replication even if the AD replication has failed with the partner for more than the tombstone lifetime. In most cases, if the server is really having the replication failure and is not caused by this unexpected time jump issue, you would see new replication errors caused by lingering objects as long as “Strict Replication Consistency” is 0x1; then no lingering objects would be really replicated out.

We will now want to follow  http://technet.microsoft.com/en-us/library/cc757610(WS.10).aspx

On the downstream domain controller where it reported the replication error code 8614 (ERROR_DS_REPL_LIFETIME_EXCEEDED), setup the “Allow Replication With Divergent and Corrupt Partner” registry value.

1. Click Start, click Run, type regedit, and then click OK.
2. Navigate to HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\NTDS\Parameters
3. In the details pane, create or edit the registry entry as follows:If the registry entry exists in the details pane, modify the entry as follows:
   1. In the details pane, right-click Allow Replication With Divergent and Corrupt Partner, and then clickModify.
   2. In the Value data box, type 1, and then click OK.

   If the registry entry does not exist, create the entry as follows:

   1. Right-click Parameters, click New, and then click DWORD Value.
   2. Type the name Allow Replication With Divergent and Corrupt Partner, and then press ENTER.
   3. Double-click the entry. In the Value data box, type 1, and then click OK.

No restart is needed. Force replication in AD Sites and Services between the destination source and destination servers.

Remember to change the “Allow Replication With Divergent and Corrupt Partner” value back to 0x0 after the issue has been sorted out.
The DC I was working on had already been rebooted and one of the DC’s had kerberos related issues, so if you have noted this yr 2000 do not reboot DC’s.Event ID 4 is logged in system errors:

The kerberos client received a KRB_AP_ERR_MODIFIED error from the server <computer name>$. This indicates that the password used to encrypt the kerberos service ticket is different than that on the target server. Commonly, this is due to identically named machine accounts in the target realm (<domain name>), and the client realm. Please contact your system administrator.

To get around this, on the problem DC where you getting this error set the Kerberos Key Distribution Center Service to manual and stop the service.

-From a command prompt on the broken DC enter the following:
netdom resetpwd /s:name_of_working_DC or PDC/ud:domain\user /pd:*
where domain\user is an administrator of the domain in the domain_name\user_name format. You will be prompted to enter your password.

And now reboot this reboot clears the Kerberos ticket cache and so clears the broken credential attempts that it has stored, one can also run klist /purge and Y to all tickets to be deleted.
Support tools and commands useful to rectify this issue

– eventviewer

-repadmin /replsum

-repadmin /showrepl

-dcdiag

-replmon.exe

support tools windows 2003 32 bit: http://www.microsoft.com/en-gb/download/details.aspx?id=15326

Windows Server 2003 Resource Kit tools: http://www.microsoft.com/en-us/download/details.aspx?id=17657