See the link to "EventID 1312 from source Active Directory" for information about this event.
To resolve this problem, access your services, mark the "Intersite Messaging" service as Automatic, and press Start.
See
ME834317 for a hotfix applicable to Microsoft Windows Server 2003.
This event, together with event 1311 from the same source may show up if the Intersite Messaging Service (ISM) is disabled. The Microsoft "Security Operations Guide for Wndows 2000 Server" states that this service can be disabled if you do not use SMTP for AD replication, but this seems to be wrong. The service is needed even if you have IP based replication.