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.