I'm thinking you likely have the old credentials saved in Windows, and its attempting to submit them before prompting you for the new ones. Can you check out the Credential Manager in Windows to see if you have a copy of your account saved there?
If you do, try removing the Outlook profile completely, purging the saved password from the Credential Manager, then adding your account once more in a new Outlook profile. That should do the trick assuming you're not currently blocked by the Intrusion Detection System for the previous password failures!
If you are, you'll see your office or device IP listed in Manage>Troubleshooting>IDS Blocks where you can unblock yourself.