I'm forwarding this from http://bugs.debian.org/689841
I was not (yet) able to look into this, so only quoting the bugreport we recieved:
Package: shelldap Version: 0.5-2 Severity: normal
Deleting attributes that do not have an equality matching rule in the schema fails. My best guess is that, in order to cope with multi-value fields, shelldap compares removed values server-side befoe deleting. Honestly, I have absolutely no clue why.
Might be related to http://bugs.debian.org/669263.