I always end up forgetting which permissions I need to grant users and where to do so when setting up terminal services... so I go googling, and end up finding the answer eventually... but I figured it's about time I left a note for myself (and others!) about which permissions you need to grant users, where they are, and why.
For starters, this article does a great job of explaining:
I'll do a quick summary of the contents, though, and borrow the images in case that site goes missing at some point. All credit goes to the original poster, of course. :P
First, there's the "Allow Logon Through Terminal Services" GPO, located under Computer Configuration\Windows Settings\Security Settings\Local Policies\User Rights Assignment\. This policy is what controls granting access to the particular machine. When you assign this GPO to a particular machine and add a group to it, that group automatically gains rights to log on to this computer, access local resources, etc. By default, Administrators and Remote Desktop Users are assigned to this policy.
Second, there's the Remote Desktop Users group. This group, as you saw above, is already a member of the "Allow Logon Through Terminal Services" security setting on most servers by default (except for domain controllers, I believe the default domain controller policy overrides this setting allowing only Domain Admins... but I could be wrong here.). The other thing this group does is grant access to connect to the RDP-TCP service on the server. You can see/change which users and groups have access to the RDP-TCP listener by opening the Terminal Services Configuration snap in and checking the Security tab, as shown below:
Finally, here's a quick recap of the typical error messages you see, and what that generally means:
1) "To log on to this remote computer, you must have Terminal Server User Access permissions on this computer..." or "The Requested session access is denied": This error means that the user that tried to connect has been assigned to the GPO correctly for "Allow Logon Through Terminal Services", but the user is not a member of the Remote Desktop Users group, or otherwise does not have permissions to the RDP-TCP listener on that machine. Go check the Terminal Services Configuration snap in.
2) "To log on to this remote computer, you must be granted the Allow Logon Through Terminal Services right..." or "The connection was denied because the user account is not authorized for remote logon." This error is pretty strait forward... the user is not assigned to the "Allow Logon Through Terminal Services" GPO.