Delay in login on Red Hat Enterprise Linux 4 system which is using LDAP authentication.

Issue

There is about a 2-3 minute delay when logging in as any user (including root, normal user, and LDAP users).  This happens on the console, SSH, and even su - to the user.  The connection happens right away and prompts for a password, once entering the password the process hangs up for a few minutes and eventually starts the session.