This is how i solved worked around it. Goal: move our LDAP servers from 10.6 to 10.9. I have spent countless hours trying to get that working.
I was so privelidged that to also move from a ldap.local domain to a new public domain. So I could afford to have a untouched, working LDAP along the way.
First try:
I exported users and groups (as text) from 10.6 and import in 10.9. Clean install of 10.9. Wildcard ceritificates from GoDaddy. Set up ONLY Open Directory. Checked that I had a proper two-way resolving DNS and set up two replicas (on virtual machines - clean install). Everything would work - UNTIL RESTART. Every single time. I read all the forums, tried a ton of solutions. Twice. Cried myself to sleep. Started all over with format and clean install. Same thing happened. Many suggested that I should avoid importing old LDAP info.
Second try:
Sooo... I started all over, format, reinstall. This time i ONLY imported the Groups - not the Users from 10.6. (The text files did look so innocent!). I typed every user from scratch, painfully paying attention to the user IDs to get a everything as close to the old LDAP. Same thing happened; everything looked good... until restart. Boom!
Final try - this worked:
Imported NOTHING AT ALL from 10.6 servers. Format, clean install, SSL certificates, reverse DNS etc. Manually typed every single user and every single group, getting every single ID right (hopefully). It now seem to work correctly and I can reboot any server or replica without returning with a damaged LDAP. OS 10.9.2 and sever 3.03. The only change between second and third try was not importing the groups from 10.6 - and that textfile is tiny!
I think there is something in the import-routine that screws this up. (this may also be triggered in "upgrade to newer version"?)
Note; I did try to upgrade a clean OS 10.9 on a virtual machine to server 3.1. CPU load goes to 100% Logs are constantly overloaded with errors. I ran away. I am not going to touch anything in a while - not until I am done with therapy after the Open Directory nightmare this has been.