Bem, o meu servidor não conseguiu descobrir como encontrar um pacote sudo, mas eu poderia do pacote ubuntu site :
wget http://security.ubuntu.com/ubuntu/pool/main/s/sudo/sudo_1.8.16-0ubuntu1.4_amd64.deb'
seguido por
dpkg -i sudo_1.8.16-0ubuntu1.4_amd64.deb
fez o truque para mim. Eu era capaz de reinstalar o pacote sudo sem sudo usando o ssh para conectar-se ao root diretamente com uma chave ssh pré-configurada.