One of the reasons I enjoy JJ2's artstyle is precisely the 256 colour palette. This forces tileset artists to use one or two main gradients that give each level its own atmosphere. All of our highly-rated tileset downloads have two colours with which you can "explain" them--"Heaven" is gold and sky blue, "Oasis" is brown and white, etc., etc. Same goes for JJ2. Now, I'm not saying that giving more colours to work with is a bad thing, but I do believe it would require unnecessary amount of work, and will change something fundamental to the game, without us knowing whether this change would be for good or not.

Moonblaze, if you've played any older sidescrollers (and I mean pre-'94), you'll know that a lot of them are ported to different platforms and computers with complete graphic overhauls. There are good examples there that a vivid world can still be beautifully represented even with an 8-colour limitation. A more modern example would be Disnay's Hercules, which got ported to PSP (IIRC), and had a lot of its sprites "cartoonified" without losing its charm.