If you added an index for an attribute in slapd.conf you have to re-index
your database. Otherwise entries are not found anymore when using
this newly indexed attribute in the search filter.

Note: This is not needed when using the new dynamic configuration
(back-config with suffix cn=config) and index configuration is changed
via LDAP modify operation. In this case a new index is automatically
generated by slapd.

Since OpenLDAP 2.x the command-line tool slapindex is used for this.

Consider an example slapd.conf like this:

database bdb (or hdb)
suffix "dc=example,dc=com"
directory /var/lib/openldap
index foo eq

Now you add another equality index for attribute 'bar':
index foo,bar eq

Now re-index your database:

1. Stop slapd

2. Re-index with this command:
slapindex -f slapd.conf -b "dc=example,dc=com" bar

3. Check whether the ownership and permissions match the user/group
slapd is running as. Look at the files in /var/lib/openldap.

4. Restart slapd

slapd does not create the index automatically after adding the line to slapd.conf. New entries will be indexed but existing entries will not. slapd will search the index for values and since the old values have not been indexed, it doesn't realize that they are they.

Solution:
Use ldbmcat to generate an LDIF for your database. Be sure to output item numbers (it is the default). Then use ldif2index to generate an index for a specific value. Restart the database and you are all set!