That was my first thought... was wondering if there were any other tricks that might help.

Namely, what is the best way to color reduce? If you just drop the pallette I suspect it doesn't look so hot, does photoshop or gimp provide an inteligent fashion to adjust the colors?