I was having the same issue and found a workaround.
In my case the problem was due to a rather weird network configuration.
LDAP server was dc.mycompany.com which resolves to (say) 10.0.10.1.
In turn my company.com has two IPs assigned: 10.0.10.1 (same as dc.mycompany.com) and 10.0.10.2.
I believe that Jenkins resolves dc.mycompany.com and then goes back to DNS name with a reverse DNS lookup yielding my company.com instead of dc.mycompany.com.
When it was time to talk with LDAP server Jenkins resolved mycompany.com and getting either 10.0.10.1 or 10.0.10.2 randomly.
If it did resolve to the "right" address things worked just fine otherwise LDAP login failed.
The workaround was to ensure that mycompany.com always resolved to the "right" address with the help of /etc/hosts.