My first guess would be licensing...if you can't connect to a Win2k terminal server from an NT4 client, your NT4 client might have an expired Temporary CAL from the terminal services licensing server. Windows 2000 systems have that CAL built-in and wouldn't be affected.
You'd either have to add some CALs to the licensing server, try a different NT4 workstation, or use a reg hack that removes the expired temp CAL from the client's registry and that would allow you to get a new 90-day temp CAL (I can dig up the link for that if it sounds useful).
Hope that helps!