It was certainly possible to add new sets, but I do recall that it could be problematic, so we avoided doing so whenever possible (and as a result I don't remember how to do it). It would be a lot easier to change colours that are already there than to add them to be honest.
vehicle_cust_color_pool.xtbl is the file that has the color data. The “sets” file had the colour palettes (groups of colors to assign to a variant). A vehicle variant references a set, which informs which colours are 'legal' for that variant. So the same car in Plesantville and the main world could have distinct paints they would spawn with (Plesantville using 'hero' 50's colours, and the same car in the world using 'standard' 50's colours).
For customization, it might work to add colours to one of the smaller pools: Candy, Pearlescent, rather than Gloss paints, although in the case of customization it's the UI that's part of the issue, since new colours would need new icons (and I have no clue how those were generated or added). Matte was rarely used, except in the case of certain special variants and spawns. I don't think we had any regularly spawning vehicles that used them (maybe the Garbage Truck as an example, I don't recall, but it would make sense that it used the Matte Municipal set). Matte paint on SR3 looked less like actual matte paint than it did on SR4, but it still wasn't particularly prevalent.
To confound things, a few of the SR4 spawning colors were made metallic, but in order to save time we just replaced existing shades (this meant we didn't need to reconfigure all the variant lists and sets to use the new colours, saving a few days work). I think we replaced gloss ones, but it may have been some of the matte ones too. All the paints were re-balanced for SR4 in addition to this, so if there's a paint in either game you want for the other game you should be able to duplicate the settings for it as I don't believe the system itself changed.
Hope that helped a little.
