The users should be assigned the Log On Locally user right in
Domain Controller Security Policy!

However, the default security settings
do not allow regular users to log on interactively at a server. You can
change this setting through Start ,Administrative Tools , Domain Controller
Security Policy. Expand Local Policies, then User Rights Assignment. Doubleclick
Allow Log On Locally and click the Add User Or Group button. In the Add
User Or Group dialog box, type in Everyone and click the OK button. In the
Security Policy Setting dialog box, click the OK button.

Hope this help..