Só testei no Conectiva 9 e 10, porém também deve funcionar para outras distribuições.

Não é possível recuperar uma senha perdida. As senhas no Linux funcionam de maneira uni-direcional e uma vez criptografadas, demora muito para se quebrar essa criptografia. O modo mais fácil é removê-la e trocá-la. Para isso, faça o seguinte:

Reinicialize a máquina!

Se estiver usando o lilo como bootloader:

Quando aparecer a tela do lilo, aperte qualquer uma das setas para interromper o carregamento automático;

Escolha a partição que contém o Linux e no prompt do lilo acrescente o seguinte comando:

rw init=/bin/bash

OBS: Se o prompt do lilo não estiver visível, aperte a tecla shift e segure por dois segundos.

Esse comando deve te levar ao shell (bash) como root.

Execute o seguinte comando:

# mount -o remount rw /

Agora edite o arquivo /etc/passwd.

Se você perdeu a senha do root, apague a segunda coluna (aquela que tem um "X") da linha que contém o usuário root;

Se você não conseguia logar por não ter um shell para cair, substitua a última coluna pelo comando: "/bin/bash";

Pronto. Salve o arquivo e saia.

Sincronize o sistema com o comando "sync".

Monte o diretório raiz de novo como somente leitura:

# mount -o remount rw /

Agora é só reiniciar a máquina e logar como root.

Feito isso, altere a senha com o comando:

# passwd

Se estiver usando o grub como bootloader:

Quando aparecer a tela do grub, aperte qualquer uma das setas para interromper o carregamento automático;

Escolha a partição que contém o Linux e aperte a tecla "e".

Na nova tela, escolha a opção que contém o kernel e aperte a tecla "e".

Acrescente o seguinte comando ao final da linha:

rw init=/bin/bash

Tecle ENTER para confirmar a inserção. Você vai voltar a tela que contém a opção do kernel. Escolha ela e aperte a tecla "b" para "bootar" nela. Isso deve te levar ao shell (bash) como root. Execute o seguinte comando:

# mount -o remount rw /

Agora edite o arquivo /etc/passwd.

Se você perdeu a senha do root, apague a segunda coluna (aquela que tem um "X") da linha que contém o usuário root;

Se você não conseguia logar por não ter um shell para cair, substitua a última coluna pelo comando: "/bin/bash";

Pronto. Salve o arquivo e saia.

Sincronize o sistema com o comando "sync".

Monte o diretório raiz de novo como somente leitura:

# mount -o remount rw /

Agora é só reiniciar a máquina e logar como root.

Se o seu problema era a senha de root, é só alterá-la agora com o comando:

# passwd

Pronto.