Eu tive o mesmo problema ao executar o instalador do vbox adições iso, mas executando sudo apt-get install virtualbox-guest-utils
funcionou bem. Eu fiz um apt-cache search virtualbox
para verificar o nome do pacote antes de tentar instalar.
No entanto, executei o comando sugerido por Gregory acima (como eu tentava fazer com que o instalador funcionasse da iso, o que nunca aconteceu), mas isso pode ou não ter tido um impacto.
Se você quiser evitar a instalação de dependências do X11, use:
sudo apt-get install --no-install-recommends virtualbox-guest-utils && sudo apt-get install virtualbox-guest-dkms
Editar: veja o comentário abaixo.