Estou tendo o mesmo problema com o Ubuntu Software com o Ubuntu 16.04, mas eu encontrei uma solução GUI fácil via "GDebi Package Installer" para que você não precise mexer na CLI com todos os seus pacotes .deb e capturará todas as dependências para que você não tenha que se preocupar em forçar o apt-get installs.
- execute "sudo apt-get instalar gdebi"
- No Nautilus, clique com o botão direito do mouse no arquivo .deb e selecione "Abrir com" - > "Instalador do pacote do GDebi"
- Selecione "Instalar pacote" para instalar.
Informações foram encontradas aqui: link