I have been running this server with LDAP for about 6 months. The logins have always been fast. However, starting this week logins are taking 1-2 minutes to complete. This include ssh, sudo su, and local logins. The Openldap database is being hosted by the server that is having the speed problems. I have two other servers that use this same openldap database for authentication, they don't have any problems with speed. The server is ubuntu server 12.04 lts running OpenLDAP 2.4.28. The two working servers are both running ubuntu server 12.04 lts also. I did notice that when logging in I get a Failed to add entry for user mbrown. Just after the login completes.
I have tried adding

UseDNS no 

to /etc/sshd_config and have also tried commenting out the line

session        optional pam_ck_connector.so nox11 

from /etc/pam.d/common-session.

Neither has sped up the login. I have also verified that my /etc/hosts file is correctly set up.

What else could be causing such a slow login?