Today I tried to get OpenLDAP going one last time. I erased the database on each machine and recompiled the code from scratch. My simple 10-person adds and deletes were working and synchronizing ok, so I was starting to think it was working. I bumped up the ldif to have 5000 names. Synchronization started up, but then things went crazy and eventually one of the servers seg-faulted. That was enough OpenLDAP for me.
I went ahead and shut down OpenLDAP and fired up FDS. In no time at all, I had a simple Master-slave replication set up and adding and removing 5000 names ( using ldapadd ) was working perfectly. I still need to get it going in a multi-master setup--looks easy enough.
My recommendation: If you're jumping into LDAP, start up with FDS.