O Ubuntu tem uma opção de inicialização de recuperação. Não sei a sua versão, você pode precisar inserir mídia de instalação e fazer o boot de renome. Isso dá um shell de root. Monte seu sistema de arquivos com senha perdida em uma nova pasta. Use o comando chroot. Então é só usar o passwd normalmente, porque o seu root vai rodar sem problemas.