As paletas de cores são todas codificadas, portanto, não é possível adicionar temas personalizados ao menu Prefs interno do gnome-terminal, a menos que você esteja disposto a corrigir o código-fonte e recompilar o aplicativo.
Uma forma de definir um tema de cores personalizado para o seu perfil é via scripts. Veja como solarize o faz:
gnome-terminal-colors-solarized
Note, no entanto, que o gconf é o EOL e as versões futuras do usarão o gsettings .