I also wish that SRB2 had no "palette", but like Shuffle said on IRC: "But, as usual, Software holds the whole god damn game back :<", it would take a whole lot of editing the entire game engine just to get a 16 million(I think thats the number) palette to work. SRB2 may have very great gameplay, but the palette limit just takes away much of the possible "atmosphere" of the game, and it also somewhat limits different kinds of level themes to have, and therefore we are stuck with the same textures, with very little ways to create new types of textures that would suit the level themes(Note that everything I said about the palette limiting level themes can be easily averted, since textures don't add anything to the gameplay, but aren't you kind of sick of seeing GFZROCK used in 50% of all SRB2 maps?).
If breaking 256 colors isn't possible, then I suggest that we make part of the current palette more "colorful." Neopal.wad is a great example of this(while it does go a little too far at making things "colorful" at times, I would take it over the Doom palette any day, and is still why I always play through SP mods with Neopal loaded(kind of abusing a bug, but Neopal doesn't make the game any easier). Plus, we kind of need to get some Cyan/Turquoise somewhere in the palette(deleting all those "useless colors" would be a great way to fit in cyan and get more purple.
Of course, all of this would delay 1.1 quite a bit, but not if STJR. gets more people to work on specific parts of the game.
I could talk more, but I'm already tired out from being up late, and typing this.