Slow Connecting to Terminal Server

I am have trouble with a few of my user connecting to Terminal Server. It just started happening. When the users click on the icon to connect to Terminal Server it says connecting to … (where ServerName is the name of the server theyare trying to connect to) this can sit on the screen up to 5 minutes before it actually connects to the Terminal Server. It use to take between 10 and 20 seconds. I am running Windows 2000 Terminal Server with Service Pack 3. Any suggestions would be greatly appreciated as my users are becoming very frusterated. Thank You in advance for your help.