Fedora directory users - Mar 2007 - "error trying to bind as user"

Alright, I have a very odd problem. I created a new user and added them to
an existing group. When they try to ssh into an environment that the group
has permissions with it works on 1 (of 3) boxes and fails on the others. The
error is as follows:

sshd[20205]: pam_ldap: error trying to bind as user
"uid=user,ou=People,dc=domain,dc=com" (Invalid credentials)

Does anyone have any idea what could be causing this issue ? Its very
frustrating cause there is no way for me to know what they will or wont be
able to log into.  ldapsearch, getent etc return the correct data.