Eu sei algumas coisas que você pode tentar. Não tenho certeza se você é novo no Linux, mas vou escrever isso para que, mesmo que seja completamente novo, você se sinta confortável com isso.
Abra o terminal com ctrl+alt+t .
(Se o terminal é intimidante, não se preocupe - você só estará copiando e colando :)
Em seguida, execute esses comandos. (Se você quiser copiá-los e colá-los, você precisa pressionar ctrl+SHIFT+v , não ctrl+v como de costume. É assim que o Terminal funciona no Linux / Ubuntu.)
sudo apt-get clean
sudo apt-get update
sudo apt-get upgrade -yr
sudo apt-get install gdebi
Esses comandos funcionam?