No necesariamente.
¿Te quedó claro que en la tabla USERS de MySQL, el algoritmo usado
no es MD5, sino un algoritmo propio de MyQSL?
Si te estás refiriendo a esa tabla, para cambiar la clave se usan sentencias de control específicas.
Lee en el manual de referencia:
http://dev.mysql.com/doc/refman/5.0/es/passwords.html
En caso de ser otra tabla,
debes averiguar cuál exactamente es la función usada para esa encriptación.