I don't know if you have found a resolution for this yet but I thought I would let you know that we had the same type of problem but it was related to specific accounts that were getting access denied. What we found was that the issue is related to the MaxTokenSize and the specific accounts that were getting the access denied. The accounts with access denied issue belonged to a large number of domain groups and their kerberos token was larger than the default of 12000 bytes which then produced the Access denied issue when trying to log onto a W2K8 R2 RDS server. The problem was resolved by changing the MaxTokenSize value in the registry to 65535 (on the W2K8 R2 RDS server) as detailed in the MS KB article 327825 "New resolution for problems with Kerberos authentication when users belong to many groups"