I have the following setup:
I have a 2 multimaster replication setup, where both masters also have a number of shadowing agreements to other consumers. The data gets replicated to all boxes and there are no issues. When I try to perform an update on the slaves, it works on all, but one. Meaning, the server sends back err=10, with the referral to one of the masters and the client automatically follows the referrals. Unfortunately, it does not works with one box:
When there is an attempt to write to the db, the server returns an error-code 1, with the following message:
javax.naming.NamingException: [LDAP: error code 1 - Mapping tree node for o=base is set to return a referral, but no referral is configured for it];
This can also be seen in the access file:

[26/Apr/2011:05:35:45 -0300] conn=3418 op=13256 ADD dn="ou=test,o=base"
[26/Apr/2011:05:35:45 -0300] conn=3418 op=13256 RESULT err=1 tag=105 nentries=0 etime=0

When I have a look at the configuration, it looks exactly like the others:

dn: cn="o=Base",cn=mapping tree,cn=config
objectClass: top
objectClass: extensibleObject
objectClass: nsMappingTree
cn: "o=Base"
nsslapd-state: referral on update
nsslapd-backend: userRoot
modifiersName: cn=server,cn=plugins,cn=config
modifyTimestamp: 20100721202730Z
nsslapd-referral: ldap://master-ld01:389/o=Base
nsslapd-referral: ldap://master-ld02:389/o=Base
numSubordinates: 1
dn: cn=replica,cn="o=Base",cn=mapping tree,cn=config
nsDS5ReplicaBindDN: cn=replication,cn=config
nsDS5ReplicaRoot: o=Base
nsDS5Flags: 0
nsDS5ReplicaType: 2
nsds5ReplicaPurgeDelay: 43200
objectClass: top
objectClass: nsDS5Replica
cn: replica
modifiersName: cn=Multimaster Replication Plugin,cn=plugins,cn=config
modifyTimestamp: 20110421052744Z
nsDS5ReplicaId: 65535
nsDS5ReplicaName: 59480b7e-94fb11df-9df8eeea-774385c0
nsDS5ReplicaReferral: ldap://master-ld01:389/o=Base
nsDS5ReplicaReferral: ldap://master-ld02:389/o=Base
I was wondering if someone has seen this kind of issue. Everything looks fine to me and I can not explain this behavior. 
Right now, I can not reproduce this issue. I only see it in this one setup.