Is this a Domain Controller or a member server on the network? On Domain Controllers, you have to make the user a member of the Remote Desktop Users on the DOMAIN in Active Directory. On a standard server, you can run lusrmgr.msc from a command prompt, open the Groups section and make the user a member of the Remote Desktop Users group there, locally on that system.
Once a user account is in that group, they can log on to the server remotely.
-tigermatt
