1. Was steht in der Datenbank? (Der Hash)
2. Wie viele Zeichen?
3. Stimmt das mit dem Ergebnis von SELECT PASSWORD('123456'); überein?
BTW: PASSWORD() ist imho nicht die beste Wahl, erst recht bei älteren MySQL-Installationen. Schau dir auch mal MD5 oder gar SHA an.
MySQL :: MySQL 5.1 Reference Manual :: 11.11.2 Encryption and Compression Functions