mysql error 1045

Hoy instalé mysql y obtuve un error al intentar acceder como root con los parametros -u root -p. La única forma de poder acceder a una base de datos era invocando mysql desde una consola con root.
Para solucionar el problema probe restablecer la contraseña de root, crear otro usuario, etc.
Sucedía una y otra vez lo siguiente:

mysql -u root -p
Enter password:
ERROR 1045 (28000): Access denied for user 'root'@'localhost' (using password: YES)

Donde obviamente yo tipeaba la contraseña correcta.

Finalmente la forma de evitar el problema fue desinstalar mysql con la opción --purge para que remueva todos los ficheros de configuración, e instalarlo de nuevo.

apt-get remove --purge mysql-server-5.0
apt-get install mysql-server-5.0