I have installed a Windows 2008 server into my Windows 2003 domain, I then enabled RDP on my Windows 2008 server verified that I could connect from my Vista client on the network. While working from home, I quickly found out that I could not RDP onto my Windows 2008 server from my 2003/XP clients. Very annoying.
The reason for this is that when I enabled RDP on the 2008 servers, I selected "Allow connections only from computers running Remote Desktop with Network Level Authentication (more secure)" Thinking that it was not a problem as I would only manage the server using Vista.
The problem was that when I took my laptop home, I was only left with 2003 and XP clients to manage the new 2008 servers. doh!
This setting means that the server requires Network Level Authentication that is only currently installed on Windows Vista or Windows sevrer 2008. You can verify that your RDP client does not support NLA, simply by running MSTSC, then on the top left hand corner, click about and then in the text you should see the section "Network Level Authentication not supported"
Guy Teverovsky wrote a nice utility – Core Configurator, which is extremely helpful in the initial configuration of Core Server. Configuring RDP is one of the options in the latest version.
Here is a video demonstration – running DCPROMO in Core Server: