Interesting stuff. This is the result produced by my "Expand Palette" Grafx2-script (It comes with the program...but this was produced with an updated/improved algorithm I think).
It "Continously fill the greatest void in the area of the color-cube enclosed by (or along ramps of) initial colors. This algorithm will create lines of allowed colors (all ranges) in 3d colorspace and the pick new colors from the most void areas (on any line)."

It probably won't produce a perfect result (whatever that may be)...but it's a good place to start if you prefer a uniform looking palette.