Try starting the rdesktop app from a terminal. If it exits it should return any messages from the server after closing the connection to the terminal to help diagnose it. It sounds like a licensing issue on the 2000 terminal server. Are you sure there are enough TS licenses and that all of the temporary ts licenses haven't been exhausted? I've found that specifying the host name in the rdp connection from the linux client to a machine known to have a license works well in a pinch.