only a handful of users cannot add or delete contacts. It gives some this error to the users desktop "This server has experienced a Directory error" Then in the Messenger console it says "unidentified Ldap error was encountered".

This server has no replicas on it, and is a 6.5sp5. The users are not restricted by the number of users they can have in their client. We have over 350 users but only a few of them cannot add the users.