http://www.lemoda.net/png/quantize/index.cgi online solution for the png palette limit. the output file is to the right of the original, be sure to scroll over to view it.

combine that with http://pixlr.com/editor/ and we can make maps right from our web browser =]

Pretty useful, thanks. Hope it can deal well with 10000x10000 maps
For those needing the color info table:
64 colours and less – the map will be displayed perfectly, with no glitches
65–96 colours – the map background sprites (falling debris, clouds, etc.) are removed; the destroyed-soil background may be glitchy
97–112 colours – destroyed soil will be transparent; the destroyed-soil border is solid gray (  #9C9D9C). The background gradient palette will be evenly loaded into the remaining space in the palette, and the background gradient is redithered using the map + background palette—thus, a map with 112 colours (bar black) will have a background gradient dithered exclusively from the map's palette.
113 colours and more – the map will not load.
Don't forget you have no limitation with ProjectX enabled :)

Thanks StepS Pac-Man

steps infected my brain with tl;dr-posts

113 colours and more – the map will not load.
I believe that with 113 colours, WA will dither the map automatically to 112 and there will be no background gradient (black only).

That must've been written before W:A automatically dithered it down. However, there's still a (fancy color) background with 112 color maps?

However, there's still a (fancy color) background with 112 color maps?
Yes, but it may or may not be nice esthetically, depending on the palette of the map. See here:
http://img805.imageshack.us/img805/2145/51909320.png

It's snowing :O

quantization is different from dithering. dithering is usually applied after quantization to defuse color bands. W:A auto dithering makes images look super speckled. quantization will produce an "optimized" palette while W:A will just create a "reduced" palette and dither the hell out of the image to fill in the missing data.

a quantized map with fewer than 112 colors will look better than a W:A dithered map at 112.