Heh, VERY old bug, never fixed. I guess they were too busy working on important things like spinning cubes. (oooh, shame on me).
However, recently, someone gave me the solution.
Actually, what's amusing is that if the LDAP server is running, even if there's no account on it, you won't get the delay--it's as if the system simply wants reassurance that yes, LDAP servers do exist in the world.
Anyway, the solution that has worked for me, gotten, I believe, on these forums....
On the client edit /etc/ldap.conf (not /etc/openldap/ldap.conf)
You will see a line, commented out, that reads bind_policy hard
Change the hard to soft (and remove the comment sign) and that should fix the issue.
In other words, change
#bind_policy hard
To
bind_policy soft