User waited until his password expired, then changed it through AD by choosing reset password option on his machine. He then logs into his machine, gets into Outlook and Messenger just fine, but get prompted for a password when accessing SharePoint, then locking the AD account. Any browser gives the same results. Clearing caches, unchecking options for password management in IE and several restarts don't solve the issue. Deleting the user's profile in SharePoint doesn't solve the issue.
The user could access SharePoint from a different computer, so it was definitely an problem specific to his machine.
It turned out that the user had a messaging application installed that managed all of the chat lists from different clients in a single place. This one was called Digsby. It was caching his password.
After uninstalling the IM Client, he restarted his computer and things worked as expected.