Problema para entrar en mysql o PhpMyadmin despues de reiniciar nuestras máquinas

Os comento un error que me he encontrado al volver a encendernos los servidores, por si os pasa a alguno más. Intentaba entrar en PhpMyadmin y me daba un error al poner el usuario y la contraseña root, también al intentar acceder desde la línea de comandos a mysql. El error es:
#2002 El servidor MySQL no autorizó su ingreso
He leido algo sobre este error y resulta que al reiniciar la máquina puede suceder. No se porque, ni como hacer para que no suceda cada vez que reinicia. Pero he econtrado como solucionarlo una vez ha reiniciado y no nos va.
Lo primero será parar el servicio mysql (probar instrucciones, dependerá de la versión del servidor) yo he usado la primera:

# /etc/init.d/mysql stop
# /etc/rc.d/init.d/mysqld stop
# service mysqld stop

Ahora ejecutamos esto:

# mysqld_safe --skip-grant-tables &

Nos conectamos a mysql:

# mysql -u root

Y vamos a cambiar la contraseña del root de mysql:

mysql> use mysql; mysql> update user set password=PASSWORD("nuevacontraseña") where User='root'; mysql> flush privileges; mysql> quit

(solo debemos cambiar en la instrucción donde pone «nuevacontraseña»,lo demás tal como está)
Para terminar de nuevo paramos el servicio y lo iniciamos, después de esto podremos acceder desde cualquiera de los dos sitios.

# /etc/init.d/mysql stop
# /etc/init.d/mysql start