LDAP auth fails for some users

Something weird is happening, some users are not able to authenticate via our LDAP to access services (SSH connection, Samba, etc.).

Their entries are in the LDAP and everything seems to be fine, I made a comparison with a working LDAP entry created with the same scripts only 5 minutes before, and the only differences I can see are the IDs/timestamps (sambaPwdMustChange, etc…)

If I do a getent passwd | grep "username" I find their record, but a ssh username@localhost fails (while again it works with other users created with the same script)

My log here /var/log/ldap/slapd.d shows error messages

Apr  9 14:09:48 je nslcd[3293]: [2fc6ce] lookup of user uid=someone,ou=People,dc=something,dc=com failed: Invalid credentials

But when I check their password on the phpldapadmin interfaces, it DOES match with the password I am entering. I am trying with a default password 123456789, which works for other users created with the same script.

Any ideas ?

EDIT 1

Authenticating with

ldapwhoami -vvv -D "uid=someone,ou=People,dc=something,dc=com" -x -W

and the password in question does return a Success (0)

EDIT 2

The authentication of these users against the same LDAP does work on many apps, like a Dokuwiki and a Rails application using the devise ldap-authenticatable gem. Only SSH and Samba seem to have problems.