Por este tipo de problemas es que nunca se recomienda hacer uso de la función password para manejar cuentas de usuario.
Para eso existe md5 o AES_ENCRYPT.
La función password no es reversible y la solución debe ser un poco rustica y requiere de la colaboración de los usuarios. Mira
esto
Mi recomendación, es realizar un update al campo contraseña haciendo uso de md5 (Con cualquier contraseña). Y ayudarse del lenguaje de programación para que permita al usuario hacer el cambio de clave nuevamente mediante la opción
olvidé mi contraseña. Cuando el usuario pinche este botón, enviar un mail con la opción de cambiar la contraseña por la elegida por el usuario y así recuperar el acceso a los usuarios.
saludos.