Você precisa do lsb-core para resolver este problema, mas este pacote não está disponível para instalação direta no 16.04.
Eu tive um problema semelhante, e eu baixei e instalei o pacote lsb-core para o Ubuntu 14.04, e ele funciona.
Tente isto:
sudo add-apt-repository "deb http://cz.archive.ubuntu.com/ubuntu trusty main" && sudo apt-get update && sudo apt-get install lsb-core
-y