This is less of an answer, and more of a repsonse to someone elses answers. You should not have to enable Log on Locally at the DC to allow users to log in to the domain. Log on locally is exactly that, gives the users the right to walk up to the DC and log on there. This is very bad from a security standpoint.
Now, if their is a policy that only allows administrators to access the computer from the network, that could be a big problem.
Creating local user accounts at all the workstations will do no good, especially if you want them to change their passwords. It will work, but creates a headache of admin work. Now you not only have to administer a domain, but local user accounts as well? And explaining to users how to change their passwords in this scenario is a pain. Not to mention if the domain account password expires, they won't know, but will just not be able to login.
So, most likely the case is that their is a policy in place that states only the administrators group can access that computer from the network. You need to change that policy to either all users, or authenticated users. My choice is authenticated users (for obvious security reasons). If you have given your users logon locally rights, I suggest taking that away, unless you want them to walk up to the DC and be able to log in. Also, you need to take your users out of the admin group, can't even believe that. I have 1 user in my admin group, me.
If you check your users properties, make sure you have not selected "user cannot change password". That is usually the case when this type of error happens. People force the user to change their password, and then don't give them the rights to do it. Very common mistake. Just being in the admin group won't give them this access, you have to make sure the check box is cleared in each individual user account.