Testei este procedimento com o versão do linux chamado de XUBUNTU e funcionou perfeitamente, acredito que seja útil para outras versões também como Ubuntu e Debian

Siga os passos abaixo:
1. inicia o sistema operacioal
2. Acesse a tela do GRUB pressione ESC ou segurando SHIFT durante a iniciação
3. Selecione a verão do Kernel que deseja alterar a senha e pressione “E” para editar
4. No final da linha que informa o Kernel, adicione rw init=/bin/bash
6. pressione Enter e em seguida b para realizar o boot ou pressiona F10

Seu sistema será iniciado com um shell sem necessidade de senha, em seguida digite o comando abaixo para redefinir sua senha:

1. passwd username
Substitua o username pelo nome do usuário que deseja alterar a senha, no caso o root.

2. digite a senha desejada

3. repita a senha para confirmar e reinicie a máquina que a nova senha está valendo.

Fonte: http://www.ubuntugeek.com/how-to-recover-password-under-ubuntu.html