Bueno, como yo deseo tenerlo siempre a mano en mi blog, voy a colocar los pasos que siempre me funcionan...
Única condición, si compilaste tu instalación, espero no haya sido con la opción '--disable-grant-options' sino esta forma no funciona.
Paramos el servicio
#sudo service mysql stop
Actualización 2019: para la versión 5.7 de MySQL es necesario crear el directorio para el lock MySQL:
sudo
mkdir
/var/run/mysqld
sudo
chown
mysql:
/var/run/mysqld
Iniciamos con todos los privilegios para todos
#mysqld_safe --skip-grant-tables --skip-networking&
2qqEntramos a la instalación como root, no nos debería pedir contraseña esta vez:
#mysql -u root
A continuación procedemos a cambiar el password de root de MySQL
mysql>use mysql;
mysql>update user set password=PASSWORD("minuevopassword") where User='root';
flush privileges;
quit;
Luego reiniciamos el servicio de MySQL.
#service mysql stop
#service mysql start