Here's an odd one: I have a site with many users, only a few of them admins. Any admin user can login either via the /admin control panel or through a frontend login, which follows the example from the documentation.
Any non-admin users will be rebuffed on either login with an "Invalid username or password" message. Even more odd, if an admin user attempts to "Login as" a non-admin user from the control panel, it simply takes them back to the dashboard with a "Logged In" message, but keeps them logged in as their original admin role.
Any ideas on what maybe to look for or test?