The color palettes are all hard-coded so adding custom themes to gnome-terminal built-in Prefs Menu is not possible unless you are willing to patch the source code and recompile the application.
One way of setting a custom color themes for your profile is via scripts. Have a look at how solarize does it:
gnome-terminal-colors-solarized
Note, though, that gconf is EOL and future releases of gnome-terminal will use _gsettings_ backend.