Not Permitting Terminal Services Logon

So your users are trying to RDP in??  If that is the case then you need to make sure that the users are part of the remote desktop users group or in My Computer properties, under the remote tab, you can add the group that you have the users in, with regards to AD.

Normally the users nead to be added to the local group "Remote Desktop Users".
The groups allowed to log on through TS is controlled by the policy "Computer Configuration\Windows Settings\Security Settings\Local Policies\User Rights Assignment\Allow log on through Terminal Services" (default Administrators and Remote Desktop Users).

Users are part of the Remote Desktop Users group.  I think a Group Policy was changed affecting this.  Is that possible?

Yes, it's the user rights assignment in my previous post that has been changed through GPO or local policy.
Use rsop.msc (Resultant Set Of Policies) to analyze what GPO is setting the policy.
Create a new GPO to set the "...\User Rights\Allow log on through Terminal Services" to allow TS-access for both Administrators and Remote Desktop Users. Link the GPO to the OU containing the TS-server.

The policy "Allow logon through Terminal Services" shows only administrators and the option of "adding" or "removing" users is greyed-out for all our servers.

I have also enabled the group policy "Allow users to connect remotely using Terminal Services" at the domain and domain controller level.  This has had no effect unfortunately.

The reason for it's grayed out is that a GPO is affecting the server. Run rsop.msc to see what GPO is applying the setting. If you were able to modify the setting, it would be overriden by the GPO.
You nead to modify the GPO (or create a new linked to the OU containing the server) to allow both Administrators and Remote Desktop Users.
Your last posts make me wonder if the server also is a DC?

A DC is affected, but the two servers running as TSs are the ones we're focused on.  

I ran rsop.msc, but it wasn't evident.  Where would the policy blocking this most likely reside?  Under Users or Computer Config?

Thanks.

User rights assignment is a part of computer configuration.

Computer Configuration\Windows Settings\Security Settings\Local Policies\User Rights Assignment\Allow log on through Terminal Services

rsop.msc is just for analyzing to find out what GPO is configuring the policy setting.

To solve the problem:
Place the TS-servers in their own OU.
Create a new GPO configuring the user right to log on through TS.
Link the GPO to the OU with the TS-servers.

Is this done via the Group Policy Management tool?  If local policies are changed via the process you've outlined, will it propogate to all the servers.

Thanks.