Executar isso em um Ubuntu 16.04 recém-instalado (instalação limpa) funciona para mim:
sudo apt-get update
sudo apt-get -y upgrade
echo debconf virtualbox-ext-pack/license seen true | sudo debconf-set-selections
echo debconf virtualbox-ext-pack/license select true | sudo debconf-set-selections
sudo apt-get -y install virtualbox virtualbox-ext-pack
Eu uso esse snippet para instalá-lo automaticamente em sistemas de teste efêmeros.
O problema de perder libgsoap8
é provavelmente sobre a execução de apt update
como eles já mencionaram no @AndroidDev.