Login into Domain

Here is a couple of things to try with the limited info given.

First check the DNS settings.
The optimal setting should be that your DNS on the workstations are set as follows:

1st = Your local domain controller
2nd = your router (ie 192.168.2.1)
3rd = your ISP's primary domain controller

Second check any software that might be trying to connect to a remote computer. I had the same problem with Checkpoint's VPN software and the fix was to change it from transparent to connect mode.

Did this always happen since this was setup? If not what changes have been made since then?

Sometimes an overly large user profile can cause huge delays in loading your personal settings. Get some of that data out and store it locally or on the server outside of the profile itself.