This error can occur if you have "pam_check_host_attr yes" in the ldapl.conf file. If you don't want per host PAM checking done, simply set this to "no".|
If you want per host PAM checking done, make sure you have the appropriate host attribute within the user's LDAP entry. Try the hostname with and without the FQDN.
If you have a user with a host attribute with an "*" to allow them to login to all hosts, and you're still getting this error, make sure DNS resolution is working correctly. I spent hours trying to figure out why one machine out of 20 was not working with LDAP authentication. Eventually I noticed that the resolv.conf file was not pointing to the correct servers, and the search string was missing. After fixing these, LDAP authentication worked as it was supposed to.