"To log on to this remote computer, you must have Terminal Server User Access permissions on this computer. By default, members of the Remote Desktop Users group have these permissions. If you are not a member of the Remote Desktop Users group or another group that has these permissions, or if the Remote Desktop User group does not have these permissions, you must be granted these permissions manually."
You can verify that the users are already members of Remote Desktop Users group and this group has the appropriate permissions.