La solución no ha tardado en llegar, esta vez San Google se ha portado bien conmigo y me dio la solución en Espacio Linux. No obstante voy a poner aquí la solución aportada por el usuario silverman al que desde aquí quiero agradecerle su aportación:
Yo uso debian, e hice lo siguiente:
shell> kill `cat /mysql-data-directory/hostname.pid`
después
shell> mysqld --skip-grant-tables &
después pon la siguiente linea:
shell> mysql -u root mysql
y al final
mysql> UPDATE mysql.user SET Password=PASSWORD('tu_password')
-> WHERE User='root';
mysql> FLUSH PRIVILEGES;
y es todo.
Reinicia el demonio de mysql, y listo!!!