Question : Cannot Remote Desktop into Server "The client cannot establish a connection to the remote computer"

I am getting the error message "The client cannot establish a connection to the remote computer" when I try to remote desktop into one of our servers.

I can still remote into all of our other servers.  
I can telnet into the server via "telnet 3389" just fine.
I can access the website hosted on this server.
I can access the server applications we use this server for just fine.
I have never had problems with Remote Desktop and this computer in the past.

Here's the steps I took to break it:
1. I upgraded some software via Remote Desktop.
2. I restarted the server via Remote Desktop.
3. there is no step 3

Ever since I restarted the server, I have not been able to remote desktop into it.  Regardless of whether I use the IP address or the server name.

We are using Windows Server 2003 on the server and Windows XP Professional on my desktop.

I have tried both the "old" and "new" Remote Desktop Clients from different computers on the network.

I am new to the network here, so any tips on troubleshooting this to narrow down where the issue is would be appreciated.

Answer : Cannot Remote Desktop into Server "The client cannot establish a connection to the remote computer"

This is a low moment for me, the solution was to reboot a third time.

Simply rebooting after updates didn't work, but logging into the machine itself, shutting down, then starting up again allowed me to use remote desktop again.