gnome-terminal é um aplicativo padrão. É instalado com o Ubuntu. Não houve necessidade de instalá-lo novamente. O termo que você usou antes era gnome-terminal .
Quando você removeu gnome-terminal , removeu outros pacotes importantes.
Você deve conseguir corrigi-lo
sudo apt-get install --reinstall ubuntu-desktop
