log on credentials are incorrect Outlook

Is the user getting in or not?
If yes, then logon is fine.
If no, then can users change their own passwords?
If users can change their own passwords, then the possibility exists that someone (either the user or someone aware of the user's old password) go into the account and changed the password so that the user cannot get in anymore. (In which case, change the password on the server to whatever the user wants it to be but make sure that he/she is following good password policies).
If users cannot change their own passwords, there's the possibility that the profile got corrupt on the server or the workstation. I'd recommend recreating the password, testing, then if all else fails... recreate the profile.