I assume the password policy and all other are correctly set. Is this happening to all users or only a specific user?
Please check this post - this might be relevant - Help | Training | Salesforce
We figured it out. The login page was for an old instance of the sandbox. Best to use test.salesforce.com after all.