Terminal server NT4 Client connection

We have a WinNT4 Domain controller and NT4 Terminal Server. We have an issue when the W2k prof. workstations are logged onto the domain and try to connect to the NT4 Terminal server they get a “timed out” message. If I make them a member of the “Domain Admin” group they successfully log onto the NT4 terminal server. Any suggestions about why this is and how er can fix it.