AD Replication Problem

AD Environment
It’s a W2K AD.  There is a root and three domains.  Each domain has multiple domain controllers.  Each domain represents a business function/company.  All domain controllers within the AD have been patched will all current Microsoft patches.  

I have two problems.
1.  I changed my GPO to force account lockout after three invalid password attempts.  All of a sudden, users started having problems with being locked out of their accounts.  Only one of the three domains is having this problem.  Most of the users swear they never entered their password but one time.  This leads to my second problem.

2.  One on my domain controllers is having problems communicating to all servers in another domain.  When I do a repadmin /showreps I get the following issue for all servers associated with that domain, which is about seven servers.

    OUNAME\server1 via RPC
        objectGuid: 16fb0d39-bbe8-4cc3-a9b2-0a302b6a8405
        Last attempt @ 2004-11-11 20:14.16 failed, result 1908:
            Could not find the domain controller for this domain.
        Last success @ 2004-10-31 11:05.29.  

I am able to ping all of the servers that the domain controller says it is having problems communicating with.  I did notice that the administrator account kept getting locked out with the policy above when I forced replication.  I turned off the policy to stop the administrator account from getting locked out.

Any ideas on how to solve these problems?

Thanks for your help!