Missing SPN causing domain replication issues

I was recently working with a customer where one of their Active Directory would not replicate. They were receiving Event ID 1645 in their Event logs:

Event Type: Error
Event Source: NTDS Replication
Event Category: Replication
Event ID: 1645
Date: 2/12/2015
Time: 11:12:15 AM
User: Everyone
Computer: DC-04
Description:
The Directory Service received a failure while trying to perform an authenticated RPC call to another Domain Controller. The failure is that the desired Service Principal Name (SPN) is not registered on the target server. The server being contacted is 3cb25b0f-3809-48fb-8571-59f4a2253846._msdcs.contoso.com. The SPN being used is E3514235-4B06-11D1-AB04-00C04FC2DCD2/3cb25b0f-3809-48fb-8571-59f4a2253846/contoso.com@contoso.com.
Please verify that the names of the target server and domain are correct. Please also verify that the SPN is registered on the computer account object for the target server on the KDC servicing the request. If the target server has been recently promoted, it will be necessary for knowledge of this computer's identity to replicate to the KDC before this computer can be authenticated.

We first identified the domain controller, you can do so by pinging the DNS URL in the Event 1645

C:\>ping -a 3cb25b0f-3809-48fb-8571-59f4a2253846._msdcs.contoso.com
Pinging DC-01.contoso.com [10.1.2.3] with 32 bytes of data:
Reply from 10.1.2.3: bytes=32 time<10ms TTL=128
Reply from 10.1.2.3: bytes=32 time<10ms TTL=128
Reply from 10.1.2.3: bytes=32 time<10ms TTL=128
Reply from 10.1.2.3: bytes=32 time<10ms TTL=128
Ping statistics for 10.1.2.3:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 0ms, Maximum = 0ms, Average = 0ms

Then we ran Setspn to add the missing SPN for DC-01. Add the replication SPN in the following form

setspn -A E3514235-4B06-11D1-AB04-00C04FC2DCD2/GUID_of_the_NTDS_settings_object/DNS_name_of_the_domain Name_of_the_domain_controller

Once we added the SPN, it starts to replicate fine and within few minutes, it was up to date.

Read my favorites blogs:

Assigning File Share permissions using Power Shell

Disk Read Error when migrating virtual machine from one cluster to another

Designing a backup less Exchange 2010 Architecture

Step by step guide for upgrading Active Directory from Microsoft Windows 2008 R2 to Microsoft Windows Server 2012 R2

Microsoft Exchange 2010 Test cases

Microsoft Exchange 2013 and ADRMS Integration