Follow-up: I was able to finish deleting and recreating the database on the second server by restarting the server (/etc/init.d/ns-slapd restart).
Hey guys... I hope I can provide sufficient detail to get a clue here, but I don't have much info about what's happening yet.
We are using Fedora DS v1.0.2, and the client is a Java application using JNDI. The client is doing some tests that involve manipulating the schema, adding/removing attributes, adding/modifying/removing object classes. During this process, objects of these types are created in the directory, too.
What's happening is that it seems like objects with duplicate names are being created, i.e. cn=object1 is created twice. The second time it gets created, its name is nsuniqueid=<alphanumeric string>. I'm not sure how this could happen, because typically if you tried to create a duplicate entry, you'd get a javax.naming.directory.NameAlreadyBoundException.
What's worse, I can't delete any of these entries. When I try to, it says "Operation not allowed on nonleaf" (doing this via the graphical console), although the object in question is a leaf. Typically, even for nonleafs, the GUI would recursively delete everything.
The only fix for this problem was to delete the underlying database behind the root suffix, and recreate it fresh. Obviously this is a serious problem, in a production environment, we can't afford to be doing something like this. This has happened on two of our servers now, and on the second one, I'm unable to even delete the database! It got halfway through, and then sits there hanging. That server is completely out of commision now.
Any information would be appreciated!!