Hola, Abre una consola y ejecuta: $ grub-md5-crypt

Te pedira la clave y comprobación de clave, luego te aparece el resultado de la clave encriptada.

Como root edita el fichero /boot/grub/menu.lst y añade a la siguiente linea el resultado del comando anterior: password --md5 resultado_de_grub-md5-crypt

Ahora debería iniciar el equipo y una vez que aparezca el menu de grub presionar p y comprobar si funciona el cambio de clave.