Case: Windows Server 2008, set up as Domain Controller. Active Directory Users added to Remote Desktop Users Group. Still, Error message says: "To log on to this remote computer, you must be granted the Allow log on through Terminal Services right. By Default, members of the Remote Desktop Users group have this right...".
Reason:
By default, Permissions are:
On workstation and servers: Administrators, Remote Desktop Users.
On domain controllers: Administrators.
Solution:
On Server, open Local Security Policy -> Local Policies -> User Rights Assignment -> Allow log on through Terminal Services -> Add group "Remote Desktop Users".
Solved.