That particular error is controlled by a local security policy setting. It is affected by both the Allow log on locally and the Deny log on locally setting.
So, log on to the local machine with a local administrator account (not domain admin or user, local admin only) and type
secpol.msc into the search or run dialog box and hit enter
In the left column
Expand Local Policies
Select User Rigts Assignment and examine who is listed for both of those policies.
You should see users and administrators groups included in allowed and they should not be present in deny (usually only guests).
Check each indivdual client machine for these settings.
If they appear to be correct and you are certain that no user is included in any group that is listed in the Deny log on locally then;
Take one of the client machines and unjoin it from the domain, join it back to a work group (anyname, workgroup is fine) then,
Check the server and make sure you remove the machine account for that computer from the Active Directory database.
Reboot the client computer, log on as a local administrator and rejoin the domain, reboot again and try to logon with domain credentials, start with domain admin account just to make sure.