Hace algún tiempo tuve problemas para resetear la contraseña de root de MySQL. Este fué el método que me funcionó:
1. Primero hay que detener el daemon de MySQL y reiniciarlo con este parametro. Esto te permitirá conectarte como root sin usar password.
/etc/init.d/mysqld stop
/usr/libexec/mysqld --skip-grant-tables
2. Selecciona la base de datos "mysql" e inserta estos valores:
INSERT INTO user
VALUES('%','root',PASSWORD('theNewPassword'),
'Y','Y','Y','Y','Y',
'Y','Y','Y','Y','Y',
'Y','Y','Y','Y','Y',
'Y','Y','Y','Y','Y','Y',
'','','','',0,0,0);
FLUSH PRIVILEGES;