this might simply be a case of them not existing in the rdp server security properties...
admin tools > terminal services configuration
right-click default-rdp, properties, security.
you can add users right there if you want, give them at least the bottom two checkmarks
or you could add a domain security group there, and then add the users thru active directory to that group.
while in those security settings there, glance around and see if any 'deny' entries didnt sneak in...