Possible solutions
1) Check DNS settings.
2) It is better to use its using the same DNS as the server i.e. local DNS not internet DNS.
3) Check for logon scripts for any errors.
4) Check Event Viewer for any errors, especially GPO's errors that could be causing the delay.
5) Check any errors on event viewer.