Hiho,
mal einfach so ind blaue geraten. Geh mal in dein Passwort-Änderungs-Script und mach dort mal direkt vor der Zeile md5($neues_Passwort) ein echo $neues_Passwort - also lass dir mal ausgeben was da wirklich verschlüsselt wird. Ich vermute mal da wirst du eine Überraschung erleben. Falls nicht (sprich falls da genau das steht, was da stehen sollte) lass dir mal das verschlüsselte Passwort ausgeben und vergleiche es mit dem was in der Datenbank gespeichert wurde. Mein zweiter Tipp wäre, das du vielleicht das bereits verschlüsselte Passwort ausversehen noch einmal durch ein md5() jagst.
Grüsse
Marc