I was setting up remote access for a user on a domain controller for some tests. This user was not an admin (but belonged to the Remote Desktop Users) and kept getting the same error message above. Setting this user to domain admin solved the problem, but of course I did not want to make any remote user a domain admin.
It so happens that it is not enough for a user to belongs to the Remote Desktop Users to gain the rights it needs. Here is how you fix this:
1.Open gpedit.msc (the local group policy editor)
2.Expand Local Computer Policy -> Computer Configuration -> Windows Settings -> Security Settings -> Local Policies -> User Rights Management
3.Look for the setting on the right called Allow log on through Remote Desktop Services
4.Double click this policy
5.Add the user/group you would like to have remote access to the box.
Once this was done, the user was able to connect w/o hassles.