I spend some time and fixed the colors of the E3 1996 Starcraft shot with interface:
This is the popular version of the screenshot from PC Gamer's website:
I used this mockup for reference, as it's so far the only high quality image of the earliest Starcraft with correct colors.
I replaced all pixels of colors that I could directly match with colors from the good image. For the remaining pixels (probably less than 5% of the image), I simply adjusted the colors by hand so they fit roughly.
Some additional thoughts regarding this screenshot:
1) I don't think I've ever seen it in a magazine aside from PC Gamer back then.
2) The nebula that begins at the far right looks different from the nebula in the other screenshots.
3) The landscape is a lot more decorated, with oozing tubes and spikes on the ground.
From this is deduce that this screenshot (probably a mockup, though the nebula might indicate otherwise) is from a different stage of development than the other E3 type screenshots.