Terminal e "Pesquisar no seu computador" não funcionam

Como dito, ambos não funcionam.
Entretanto consigo usar normalmente o terminal pelo tty, além de o terminal dentro do Visual Studio Code também funcionar, entretanto quando tento abrir o terminal sem intermediários não há resultado.

O da pesquisa quando clico aparece “Desculpe não há nada que corresponda a sua pergunta”, mesmo sem eu ter digitado nada.

Eu dei apt-get remove gnome-terminal (tentei o uninstall, mas fala que não é um comando válido).
Quando vou dar apt-get install gnome-terminal, aparecem que diversos pacotes não tem atualmente ficheiros