De acordo com a saída de apt-cache policy gnome-terminal , você instalou gnome-terminal 3.10 via PPA e gnome-terminal 3.6 ainda está disponível no repositório principal. Então faça o downgrade de 3.10 para 3.6, execute o seguinte comando:
sudo apt-get install gnome-terminal=3.6.2-0ubuntu1
Aqui está outro método que envolve a remoção do PPA:
sudo apt-get install ppa-purge
sudo ppa-purge ppa:gnome3-team/gnome3