Although there is a similar question at Unix&LInux, I can perhaps add some new information and expand some of the points made there in order to give you a few useful pointers. However, it is true to say that you cannot add another 'built in' scheme to the menu as those existing ones are defined in the source code, as you can see if you examine the latest code release.

You could of course patch the source to include your scheme in the choices and then compile the program, but there are some other alternatives which centre around scripting and which I discuss further below.

If you created a color scheme by experimenting with the menus (as in the screenshot below),

you could back it up by noting the instructions in this answer:

• How to store my gnome terminal color palette

Or you could run gconftool-2 -R /apps/gnome-terminal >> file.txt and then use those values in the resulting text file as the basis for a script. A script would be best, as it would be tedious to manually reapply those values by using gconftool-2 or even by editing the .xml file from the correct profile in /home/mike/.gconf/apps/gnome-terminal.

So it seems that scripting is the easiest way to apply or reapply your color scheme settings to any gnome-terminal profile of your choice.

A good model could be provided by the solarised color scheme, which is itself based on the work here. As noted at the github page,

In Gnome terminal, you can add or edit profiles from the menu bar. However,
this functionality is not easliy available from command line. Here, you'll
find a script that will set the palette colors, foreground, background and
highlight colors to a light or dark color scheme, overwriting a color profile
you choose.

It would seem to be possible to adapt the method used for scripting the solarised color scheme, and substitute your own color palettes, etc. After running in terminal

git clone git://github.com/sigurdga/gnome-terminal-colors-solarized.git

and then using cd to get to the resulting folder, you could examine the scripts and files. In the gnome-terminal-colors-solarized folder, there is a script called install.sh in which gconftool-2 is used to apply the values which are specified in the files in the color sub-folder.

It should be possible to create your own custom profile and then change the values of the files in the colors folder, and tweak the scripts if necessary, and then you should be able to apply and reapply your own color scheme, just like you can with the solarised scheme.

If you want to produce a really interesting and original color scheme you might need to do some reading and research from here and other sources on terminal color schemes, and which are best for long periods of terminal usage.