Description of problem:

Password Policy Entry:
  dn: cn="cn=nsPwPolicyEntry,ou=People,dc=example,dc=com",
   cn=nsPwPolicyContainer,ou=People,dc=example,dc=com
  ...
  passwordInHistory: 6
  passwordHistory: on
  ...

$ ldapmodify -x -h localhost -p 389 -D 'uid=nd,ou=People,dc=example,dc=com' -w testpassword
dn: uid=nd, ou=People, dc=example, dc=com
changetype: modify
delete: userPassword
userPassword: testpassword

modifying entry "uid=nd, ou=People, dc=example, dc=com"
ldap_modify: Constraint violation (19)
	additional info: password in history

Note: if the value is not given, you can delete the password(s).
$ ldapmodify -x -h localhost -p 389 -D 'uid=nd,ou=People,dc=example,dc=com' -w testpassword
dn: uid=nd, ou=People, dc=example, dc=com
changetype: modify
delete: userPassword

modifying entry "uid=nd, ou=People, dc=example, dc=com"

Place the Constraint violation is being set:
(gdb) bt
#0  check_pw_syntax_ext (pb=0x22b8ac0, sdn=0x7f6750eefbc0,
    vals=0x7f671c008590, old_pw=0x7f6750ef1c68, e=0x7f671c001630, mod_op=1,
    smods=0x7f6750ef1c70) at ldap/servers/slapd/pw.c:1014
#1  0x0000003542689980 in op_shared_allow_pw_change (pb=0x22b8ac0,
    mod=0x7f671c0044d0, old_pw=0x7f6750ef1c68, smods=0x7f6750ef1c70)
    at ldap/servers/slapd/modify.c:1165
#2  0x0000003542687aa6 in do_modify (pb=0x22b8ac0)
    at ldap/servers/slapd/modify.c:353
#3  0x0000000000413ac4 in connection_dispatch_operation (conn=0x7f67522fd410,
    op=0x2658b10, pb=0x22b8ac0) at ldap/servers/slapd/connection.c:583
#4  0x00000000004152d4 in connection_threadmain ()
    at ldap/servers/slapd/connection.c:2328
#5  0x0000003262429633 in _pt_root (arg=0x2652ea0)
    at ../../../mozilla/nsprpub/pr/src/pthreads/ptthread.c:187
#6  0x0000003252807761 in start_thread (arg=0x7f6750ef2700)
    at pthread_create.c:301
#7  0x00000032520e098d in clone ()
    at ../sysdeps/unix/sysv/linux/x86_64/clone.S:115

(gdb) p **va
$3 = {bv = {bv_len = 46,
    bv_val = 0x7f671c000a20 "{SSHA}hUBeG9p/rwgLj7WmNZwJcganEQ8eWvLYPsOQ2w=="},
  v_csnset = 0x7f671c003880, v_flags = 0}
(gdb) p *vals[0]
$5 = {bv = {bv_len = 12, bv_val = 0x7f671c007160 "testpassword"},
  v_csnset = 0x0, v_flags = 0}