Event ID 2042 & 1925 = Replication problems

Started work for a new company last week which has a 2003 server domain.
Forest and Domain Functional level is set to 2003.
SP1.

They have 4 sites throughout the UK all in the same domain and 2003 etc as above.
3 sites replicate back and forth fine.
One site however in London does not replicate.
Can ping the site via netbios and ping from the site to all other sites via netbios.
Below are the event IDs from one of the DCs in one of the sites which is trying to replicate to the London site.

Event Type:      Error
Event Source:      NTDS Replication
Event Category:      Replication
Event ID:      2042
Date:            06/02/2008
Time:            10:10:27
User:            NT AUTHORITY\ANONYMOUS LOGON
Computer:      DC01
Description:
It has been too long since this machine last replicated with the named source machine. The time between replications with this source has exceeded the tombstone lifetime. Replication has been stopped with this source.
The reason that replication is not allowed to continue is that the two machine's views of deleted objects may now be different. The source machine may still have copies of objects that have been deleted (and garbage collected) on this machine. If they were allowed to replicate, the source machine might return objects which have already been deleted.
Time of last successful replication:
2007-06-27 16:55:52
Invocation ID of source:
03cdf820-f810-03cd-0100-000000000000
Name of source:
7a27f6db-f61c-45b4-a7f8-ba91a8249653._msdcs.domainname.local
Tombstone lifetime (days):
60
 
The replication operation has failed.
 
User Action:
 
Determine which of the two machines was disconnected from the forest and is now out of date. You have three options:
 
1. Demote or reinstall the machine(s) that were disconnected.
2. Use the "repadmin /removelingeringobjects" tool to remove inconsistent deleted objects and then resume replication.
3. Resume replication. Inconsistent deleted objects may be introduced. You can continue replication by using the following registry key. Once the systems replicate once, it is recommended that you remove the key to reinstate the protection.
 Registry Key:
HKLM\System\CurrentControlSet\Services\NTDS\Parameters\Allow Replication With Divergent and Corrupt Partner


For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.


WARNING WHICH GOES WITH THE ABOVE ERROR

Event Type:      Warning
Event Source:      NTDS KCC
Event Category:      Knowledge Consistency Checker
Event ID:      1925
Date:            06/02/2008
Time:            10:10:27
User:            NT AUTHORITY\ANONYMOUS LOGON
Computer:      DC01
Description:
The attempt to establish a replication link for the following writable directory partition failed.
 
Directory partition:
DC=domainname,DC=local
Source domain controller:
CN=NTDS Settings,CN=londonserver,CN=Servers,CN=london,CN=Sites,CN=Configuration,DC=domainname,DC=local
Source domain controller address:
7a27f6db-f61c-45b4-a7f8-ba91a8249653._msdcs.domainname.local
Intersite transport (if any):
CN=IP,CN=Inter-Site Transports,CN=Sites,CN=Configuration,DC=domainname,DC=local
 
This domain controller will be unable to replicate with the source domain controller until this problem is corrected.  
 
User Action
Verify if the source domain controller is accessible or network connectivity is available.
 
Additional Data
Error value:
8614 The Active Directory cannot replicate with this server because the time since the last replication with this server has exceeded the tombstone lifetime.

For more information, see Help and Support Center at http://go.microsoft.com/fwlink/events.asp.


Any tips or heads up on this appreciated as I have now got to get this corrected pretty quickly, so any tips advice appreciated.