Ну, мой сервер не мог понять, как найти пакет sudo, но я мог узнать это с сайта пакета ubuntu :
wget http://security.ubuntu.com/ubuntu/pool/main/s/sudo/sudo_1.8.16-0ubuntu1.4_amd64.deb`
с последующим
dpkg -i sudo_1.8.16-0ubuntu1.4_amd64.deb
сделал трюк для меня. Я смог переустановить пакет sudo без sudo, используя ssh для прямого подключения к root с предварительно настроенным ключом ssh.