Esto lo copio de otro blog porque me sirvio al 100%.
http://www.codigomaestro.com/mysql/recuperar-contrasena-root-de-mysql/

La unica diferencia es en el paso2, eso queda corriendo en una termina, y luego abro otra para el paso3, el resto esta todo bien.

Recuperar contraseña root de MySQL

Publicado por admin el 18 de junio de 2008 en MySQL
Usted puede recuperar la contraseña del servidor de base de datos MySQL con los siguientes pasos:
Paso 1: Detener cualquier proceso del servidor MySQL.
Paso 2: Iniciar el proceso del servidor MySQL (mysqld) con la opción –skip-grant-tables por lo cual este no preguntará por la contraseña.
Paso 3: Conectar al servidor MySQL como el usuario root
Paso 4: Configurar una nueva contraseña para la nueva contraseña root
Paso 5: Salir y reiniciar el servidor MySQL

A continuación están los comandos necesarios para cada uno de los pasos mencionados anteriormente (iniciar sesión como el usuario root):
Paso # 1: Detener el servicio mysql

# /etc/init.d/mysql stop

Salida:
Stopping MySQL database server: mysqld.
Paso # 2: Iniciar el servidor MySQL sin contraseña:

# mysqld_safe --skip-grant-tables

Salida:
[1] 5988
Iniciando el motor de mysqld de las bases de datos desde /var/lib/mysql
mysqld_safe[6025]: started
Paso # 3: Conectar al servidor mysql usando el cliente mysql:

# mysql -u root

Salida:
Bienvenido al monitor de MySQL.  Comandos y con ; o \g.
Your MySQL connection id is 1 to server version: 5.0.21-log
Tipiar ‘help;’ o ‘\h’ para obtener ayuda. Tipiar ‘\c’ para en vaciar el buffer.
mysql>
Paso # 4: Configurar una nueva contraseña del servidor MySQL para el usuario root:

mysql> use mysql; mysql> update user set password=PASSWORD("NEW-ROOT-PASSWORD") where User='root'; mysql> flush privileges; mysql> quit

Paso # 5: Detener el servidor MySQL:

# /etc/init.d/mysql stop

Salida:
Stopping MySQL database server: mysqld
STOPPING server from pid file /var/run/mysqld/mysqld.pid
mysqld_safe[6121]: ended
[1]+  Done                    mysqld_safe –skip-grant-tables
Paso # 6: Iniciar el servidor MySQL y verificar la contraseña:
# /etc/init.d/mysql start
# mysql -u root -p