Tem certeza de verificar primeiro a autenticação local e depois o back-end do LDAP?
Verifique seu /etc/nsswitch.conf
Ele deve mostrar:
passwd: arquivos ldap grupo: arquivos ldap shadow: arquivos ldap
ou talvez também a opção "compat"
Editar:
O nscd tem sido uma fonte de problemas em minhas máquinas RHEL, criando bugs onde você nunca esperaria um do nscd. Então a resposta é sim, o nscd pode ser a causa desse comportamento estranho. Você deve tentar limpar o cache do nscd durante seus testes.
nscd -i passwd nscd -i group