Faction color options for multiplayer and skirmish games are defined in multiplayer.ini. They are listed at the end of that file. To add new ones, just follow the same principles as the existing ones, but (of course) change the color values and then add a new entry in generals.csf or generals.str (whichever you use) for your new color option.
There is one thing you might notice, though. With your new color choices the color of the progress bars on the load screen will not match. Deezire successfully added a new progress bar for brown in Pro:Gen, so I know it's possible. I haven't tried it myself, but I'm guessing it involves, among other things, editing the .wnd file for the load screen.