OpenLDAP/SSH : sshd[1414]: fatal: login_get_lastlog: Cannot find account for uid 1000

Since several months after a upgrade from OpenLDAP 2.4.11 to the most 
recent one I have trouble login in on machines which authenticate users 
via OpenLDAP.

The OpenLDAP server is at the momen a FreeBSD 7.2 box running most 
recent OpenLDAP from ports. The follwoing is also true for each OpenLDAP 
2.4.16 I've running on most recent FreeBSD 8.0-CURRENT boxes.

I can't login via ssh anymore! For first circumvention of the problem I 
installed local users, so I can login via them.

Here what I can and what not:

I can enumerate each user in the OpenLDAP DIT via id I wish
I can use the OpenLDAP server to login on a samba share
I can 'su' to users having their account stuff in the OpenLDAP DIT

Whenever I (or any other user) try to login to a host which does 
PAMyfied authentication to LDAP servers (whihc worked weeks ago 
perfectly), I (or he) gets this:

sshd[1414]: fatal: login_get_lastlog: Cannot find account for uid 1000

Loggin the console messages on the server shows this:

sshd[482]: nss_ldap: could not search LDAP server - Server is unavailable

sshd[482]: fatal: login_get_lastlog: Cannot find account for uid 1000


I tried to reconfigure /etc/ssh/sshd_config on the host side, restored 
it with a version that worked long before and then tried to reconfigure 
it by scratch, beginning from default. No success.
Due to the fact other services can autheticate without problems via 
LDAP, this must have to do with SSH and/or the way it is implemented in 
FreeBSD.

Please help.

Regards,
Oliver