So I was editing the Quake palette, specifically the last ramp before the fullbrights with the horrible saturated blues.
https://dl.dropboxusercontent.com/u/15588722/post/func_msg/quakepals.png
What I did was just extrapolating the ramp back from the colours on the right side of the ramp.
This is likely what this ramp looked like before someone decided that they needed the Dopefish secret.
I am pondering using this for my textureset, though I wonder if I should make it mandatory or if I should make an extra wad with all the textures that make use of the new colours (probably not that many, seeing as the difference of this blue ramp to the other blue ramp is similar to the differences between the 2 purple ramps.)