Quick answer:
In Windows 7/8/10, we use a third-party Credential Provider, and it was blocking LOCAL (ie. not Domain) accounts from logging on. Removing the third-party CP resolved the issue. (we have logged a fault with the vendor).
Detailed answer follows:
If you search for the answer on the internet, you’ll see an answer like this:
This can happen if the desktop policy titled Access this computer from the network has been modified from the default values and that the users and groups listed in this policy no longer contain the user or group entries for the particular user logging on. This normally won’t happen as the default values for this policy include “Users” and “Everyone” access groups.
To resolve this issue, edit the Access this computer from the network local policy on the desktop to restore the “Users” access group or add one or more user and group values to provide the required access. Alternatively this can be configured using Group Policy.
These configuration settings are found under Computer Configuration > Windows Settings> Security Settings > Local Policies > User Rights Assignment.
What the “Access this computer from the network” setting does, is give the user account, the SeInteractiveLogonRight user privilege. I used AccessChk to see if the LOCAL account had that privilege.
It did.
So what could be interfering with logon privileges? I remembered a similar case with a third-party GINA and thought, “hang on, we’re using a third-party CP”.
Removing it solved our issue.