Are multiple domains and a trust relationship involved?
I have seen the same thing happen in both of the following circumstances:
a) Two separate domains, with a trust relationship (I think it was a two way trust, but that was a few years ago). Same account in both domains with the same password.
Solution, rename the account in one domain or change the password for one account.
b) Two separate domains with no trust relationship. Same account name in both domains, but different passwords.
Solution, rename one account or change password for one account so that it matches the other.
If you recently created or broke a trust relationship, I would suspect that one of the above situations is your problem.