The skybox's shouldn't be tied to maps (at least I have never heard of this happening)....
If memory serves me correctly, there are these colored skyboxes:
Purple - Almost entirely purple, very nebula/cloud like background, and my personal favorite
Light Green - Almost entirely green, similar to the purple with a very nebula/cloud like background, though there is an area that is mostly white (probably the center of the galaxy)
Dark blue - Almost entirely blue, again very nebula/cloud like, but this one has a significant area that is bright white, likely the center of the galaxy...the blue in this one is pretty dark, much different than the other blue...
Light blue - Mostly a bright blue, but the entire "horizon" is a thin brown/gold band, and there is a small area with more white, again likely the center of the galaxy...this blue is pretty light, so it shouldn't look like the other blue background at all...
Orange - Varies between red-orange patches of cloud/nebula and brighter orange-yellow background
Red - Similar to orange, but less variety; more of a consistent red-orange sort of wispy cloud/nebula background with a few patches of bright white...
If you are unable to get one of these to appear, there are likely two reasons...
One, you confused one with another...the two red/orange ones are similar to someone that isn't an aesthetic, and the blue I suppose might be confused, though they are fairly different
However, the most likely possibility is seeding...I'm not a computer expert, but I know randomness is created in games by generating a seed and then using that seed to simulate randomness...the seed is likely generated when the game is started, and if there are long streaks in that seed, then you may generate the same backgrounds over and over with little variety...
If you simply toggle the colored skybox checkbox under effects enough times, you should eventually get to any background you want, even with a bad seed...if you've clicked the checkbox a million times and still have not gotten the background you want, I suppose you could restart the game, but this situation seems really unlikely...
I have noticed that when changing the faction of an AI player, it stays with a certain picture set (one different picture for each race)...toggle off the player, then back on can change the picture set, however I will say that no matter how many times you do this only about 3 or 4 of the 6(?) or so picture sets seem to be useable for each player slot...I don't think this is done for skybox's (there's only like 6 colored ones) but I could be wrong...restarting the game should reset the seed...
As a note, skybox is tied to each individual system, not to a game or map...therefore, if you play on a map with multiple systems, you can have multiple skybox's on the same map...also, you must be zoomed into a system to see the skybox, zooming out will just show black space...