Exchange 2000 error on Recipient Update

When I try to add a new domain to the recipient update service I get this error message:
Only one instance of the Recipient Update Service can update a domain controller and all domain controllers on ‘xyz.domain.net’ are already being updated.
ID no: c1039c6c

I have ran domainprep on the DC and the DC has never been added the the update service.