Since this is bash, I decided to help out a bit here, bash is great

First things first, you asked for a good palette, well, I have one that I made for mirrow. It has the default colours and some extra stuff like browns, oranges, blues, yellows, greys, light blues, pinks, greens etc. etc. It has the snow fixed in it, it also has working colours for 2 textured backgrounds. To make them really work just remember to add all 32 colours of the chosen gradient into your tileset or evil JCS won't add them to your tileset file. Don't know what a gradient is? it's simple, just a set of colours ranging from one colour to another. Janus Jacrrabbit explained a simple one. Anyways, here's the link to the palette:
http://users.surfanytime.co.uk/disguise/mirrow.pal

I also added this palette to an 8-bit (yes images must be 8-bit and the first bit of the palette must look like the original jazz palette in order for it to work) image. It's nice and big, so i doubt you'll run out of tiles to use, also uploaded and you can download here:
http://users.surfanytime.co.uk/disguise/Mirrow.pcx

The palette was made with Palsuite, the same program BlurredD gave a link to earlier on. If you can't find it the link is here:
http://www.geocities.com/alister_j_t/PalSuite/Index.htm
I used that program to make a lot of things and edit palettes. I even used it to make the palette I mentioned above. Every tileset I made after Metal Mania (except the ones using default palette) has had that proggie make a palette for it. In this message a BIG thanks to toxic bunny and all the work he put into it, heck, this is the best palette editing proggie out there and we owe it all to TOXIC BUNNY!!! WHOOHOO! YEAH!!! THANKS MAN!!! YOU ROCK!! If you had the lsightest bit of any idea how much time and effort it saved me you would download it now even if you have no clue what on earth it does and how it works.

Apart from that all you need is the texture maker, well, the one Rage mentioned is cool, I used to use it, until I got a BRAND NEW COOLER ONE!!! Teralogic Texture Maker it's called. That is also uploaded onto my 'internet hard drive'. It's freeware so don't give me a bad time about distributing illegal files. It is a full working version and it's very rare cuz the company that made it made a newer program that they're charging for and they like to see this one down the drain cuz it does the job just as good (better IMO)
http://users.surfanytime.co.uk/disguise/TTM32.zip
just extract that sucker into a directory and ur off, it has a great tutorial with it in html format that can get you making textures in no time! Heh, I suppose I should give some examples to 'sell' the product.
Teralogic Texture Maker has made tons of textures for my tilesets. First that used it is the background in Spacey Universe, later it also made backgrounds for Fishy, Nature's Ruins, and Corrupted Sanctuary. Wanna see what it does? go check those tilesets out!

There, that should be all, got any problems with my uploads, tell me and i'll reupload, I'm glad I did cuz this should remove some traffic in my instant messengers