OpenLDAP complains that the fields are not indexed

Its complaining you need SUBstring indexes, not just equality indexes. You can add them with the "sub" keyword. For example:

olcDbIndex: cn,mail,sn sub,eq