Então, eu estava executando testes em algo que configurei para isso e acho que encontrei o problema. Isso foi frustrante.

http://dev.mysql.com/doc/refman /5.0/en/password-hashing.html

Dos documentos na função PASSWORD():

"Para acomodar hashes de senha mais longos, a coluna Senha na tabela de usuários foi alterada neste momento para 41 bytes, seu comprimento atual."

Meu campo de senha na minha coluna de usuário estava armazenando apenas 25 bytes, então uma PASSWORD() da minha senha falsa 'asdfasdf' estava gerando "*1B1A59A0792309FDE6F1A8681D2B58C4F2639156", mas minha tabela estava armazenando apenas "*1B1A59A0792309FDE6F1A868" devido à falta de espaço de armazenamento.

Tenho certeza que você pode adivinhar o resultado da comparação desses dois.

Este pode não ser o seu problema, mas pode ajudar algum outro indivíduo pobre e quebrado no futuro.