Check list when troubleshooting remote desktop connections:

1-try connecting using the IP of the remote computer not the computer name

2-"allow users to connect remotely to this computer" must be enabled

3-you must be a member of the remote desktop users group, of the local machine, (administrators are by default)

4-to further confirm the above, open the terminal services configuration manager under administrative tools, click on connections and in the right hand window there should be RDP-Tcp... If not you need to create the connection. Right click on "connections" choose create new connection and follow the wizard

5-assuming the connection above exists, right click on RDP-Tcp and choose properties and then permission. Make sure the user, or a group to which they belong is listed and has at least user and guest access

6-also in the terminal server configuration manager above, make sure there are no corrupt accounts, under permissions. They will be shown as S-123-1234-1234  (S and a series of - and #'s). If any exist, you will need to delete them and re-add the group

7-if the computer is a member of a server 2000/2003 domain you will have one of the 2 following check boxes, depending on the version, on the "Terminal Services Profile" of the users profile in Active Directory. Make sure it is checked appropriately. "Deny the user permission to log on to any terminal server", or "Allow Logon to Terminal Server"

8-if XP SP2 or Server 2003 SP1 the firewall needs to be configured to allow remote connections ( I would disable for now for troubleshooting purposes)

9-make sure any other software firewalls are disabled as well (for test purposes), including Internet security suites. Symantec's sometimes needs to be uninstalled or if using Symantec Antivirus some versions have "Internet Worm Protection" which can block Remote Desktop. Try disabling that as well.

10-Verify the Remote Desktop User group has the rights to log on using Terminal Services.  Go to Control Panel | Administrative tools | Local Security Policy | Local Policies | User Rights Assignments ...make sure Remote Desktop Users is included in "allow logon through Terminal Services" 

11-if this is a domain controller you will also have to edit the Domain Controller Security Policy under the server's administrative tools. As above, in this policy, go to Domain Controller Security Policy | Local Policies | User Rights Assignments ...make sure the user or a group to which they belong, such as the Remote Desktop Users is included in BOTH "allow logon through Terminal Services" and allow "logon locally"

12-The terminal Services service must be running

If you have access to the remote machine make sure it is "listening" for your connection. To do so at a command line enter (substitute port # if not using default 3389):

  netstat  -an  |find  "3389"

You should get the following result:

TCP   0.0.0.0:3389    0.0.0.0:0    listening

If not go to Start  | Run | services.msc and see if Terminal Services is started and set to automatic

13- If unable to access Remote Desktop Session from a Vista PC see "Issues with Remote Desktop and Vista"