We had to create the correct index for that.
As said here, first stop the service :
sudo service slapd stop
Then edit /etc/ldap/slapd.d/cn=config/olcDatabase={1}hdb.ldif
and add (just after line olcDbIndex: objectClass eq
) :
...
olcDbIndex: uid eq
olcDbIndex: member eq
olcDbIndex: mail eq
olcDbIndex: cn eq
...
Then re-index, set the correct rights and restart the service :
sudo slapindex -F /etc/ldap/slapd.d
sudo chown -R openldap:openldap /var/lib/ldap
sudo service slapd start
sudo service apache2 restart