bind fails with err=32 until binding object is queried

[Jesse Defer]

I have a multi-master 389 directory setup, two are 1.2.11.25 (RHEL5) and
two are 1.2.11.15 (RHEL6).  The RHEL5 servers have been running for
years without issue, while we recently created the RHEL6 servers and
initialized them from the existing ones.  One of the .15 servers
exhibits a strange issue where I can't bind as a user (err=32) until I
first search for the user.  Every time I restart it I have to perform a
search otherwise none of my users can bind.  Any suggestions?

Occasionally I get these errors on all 4 of the servers, but nothing
else:
[28/May/2014:16:39:43 -0700] _entry_set_tombstone_rdn - Failed to
convert DN uid=myuserid to RDN
[28/May/2014:16:39:43 -0700] id2entry - str2entry returned NULL for id
11, string="rdn"

Example of failure:

# ldapsearch -x -h localhost -D
"uid=myuserid,ou=ReadOnly,o=mydomain.edu" -w 'xxxxxx' -b
"o=mydomain.edu" uid=myuserid
ldap_bind: No such object (32)
    matched DN: ou=ReadOnly,o=mydomain.edu

# ldapsearch -x -h localhost -b "o=mydomain.edu" "uid=myuserid"
# extended LDIF
#
# LDAPv3
# base <o=mydomain.edu> with scope subtree
# filter: uid=myuserid
# requesting: ALL
#

# search result
search: 2
result: 0 Success

# numResponses: 1

# ldapsearch -x -h localhost -D
"uid=myuserid,ou=ReadOnly,o=mydomain.edu" -w 'xxxxxx' -b
"o=mydomain.edu" uid=myuserid
# extended LDIF
#
# LDAPv3
# base <o=mydomain.edu> with scope subtree
# filter: uid=myuserid
# requesting: ALL
#

# myuserid, ReadOnly, mydomain.edu
dn: uid=myuserid,ou=ReadOnly,o=mydomain.edu
uid: myuserid
objectClass: top
objectClass: person
objectClass: organizationalPerson
objectClass: inetOrgPerson
sn: myuserid
cn: myuserid

# search result
search: 2
result: 0 Success

# numResponses: 2
# numEntries: 1

Thanks,
Jesse DeFer