Tuve unos problemas tratando de acceder a un servidor del que nadie recordaba la contraseña, finalmente luego de googlear un rato y tratar de recuperarla con el sistema de reparación (lo cual resultó infructífero), encontré que se hace de la siguiente manera:

Cuando carga el bootloader (grub o lilo) editamos los parámetros de arranque del kernel, para que ademas de lo que ya trae, tenga

init=/bin/sh

Esto nos hará entrar automáticamente a la consola como root, desde la cual ya podemos cambiar la contraseña con el comando passwd