O suporte a 24 bits é ativado por padrão mas gnome-terminal
tem que estar na versão vinculada a libvte >= 0.36
(conforme indicado na página que você mencionou). Que infelizmente não é o caso no ubuntu 14.04 mais recente (no momento da escrita).
Como solução alternativa, você pode tentar:
sudo add-apt-repository ppa:gnome3-team/gnome3-staging
sudo apt-get update
sudo apt-get install gnome-terminal
sudo add-apt-repository -r ppa:gnome3-team/gnome3-staging
O último passo remove o seu ppa - é opcional mas tenha cuidado, existe todo o gnome3 nesse ppa.
Ah e a tela: