To complete this procedure, you must be a member of the local Administrators group.

To enable Remote Desktop remotely by using the registry

1. On any computer that is running a version of Windows Server 2003 or Windows XP Professional, click Start, click Run, type regedit, and then click OK.

2. On the File menu, click Connect Network Registry.

3. In the Select Computer dialog box, type the computer name and then click Check Names.

4. In the Enter Network Password dialog box, provide Domain Admins credentials for the domain of the server, and then click OK.

5. After the computer name resolves, click OK.

6. In the computer node that appears in the Registry Editor, navigate to HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Control\Terminal Server.

7. In the console tree, click Terminal Server and then, in the details pane, double-click fDenyTSConnections.

8. In the Edit DWORD Value box, in Value data, type 0, and then click OK.

In the Microsoft TechNet article they say you need to do a remote reboot in order to have the changes to work, in a testcase, the reboot was not necessary.

Source: Microsoft TechNet.