Description of problem:

Steps:
passwordInHistory: 3

Original password is testpassword --> passwd-001
$ 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
replace: userPassword
userPassword: passwd-001

Repeat this as follows:
passwd-001 --> passwd-002
passwd-002 --> passwd-003

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

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

Change password one more time.
$ ldapmodify -x -h localhost -p 389 -D 'uid=nd,ou=People,dc=example,dc=com' -w passwd-003
dn: uid=nd, ou=People, dc=example, dc=com
changetype: modify
replace: userPassword
userPassword: passwd-004

Then, try the original password.  It works.
$ ldapmodify -x -h localhost -p 389 -D 'uid=nd,ou=People,dc=example,dc=com' -w passwd-004
dn: uid=nd, ou=People, dc=example, dc=com
changetype: modify
replace: userPassword
userPassword: testpassword

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

http://docs.redhat.com/docs/en-US/Red_Hat_Directory_Server/8.2/html/Configuration_and_Command-Line_Tool_Reference/Core_Server_Configuration_Reference.html#cnconfig-passwordInHistory_Number_of_Passwords_to_Remember
3.1.1.127. passwordInHistory (Number of Passwords to Remember)
Indicates the number of passwords the Directory Server stores in history. Passwords that are stored in history cannot be reused by users.