Ever play with the indexed colour custom colour tables ansd think 'gee, those colours look neat, but the GIF dithering bites?'

Here's a simple solution:
Convert your original image (pic 1) to indexed colour using a custom colour table. For instance, select Black Body (pic 2).
Once it's converted, select all and copy.
Revert the image (or at least jump back to before you converted it to indexed colour inthe history palette)
Paste
Run a 1.0 gaussian blur on the pasted layer
Change the merge mode on the layer to 'colour'
Viola.

For more fun, make your own custom colour tables. Simply open a new document, make a gradient using the colour range you want, and run the gradient. Convert the image to Indexed Colour using a perceptual or selective palette. Then go to Image->Mode->Colour Table and save the colour table to a photoshop ACT file.

With your picture, do as above, but instead of selecting a preset palette, click 'load' and browse to your ACT file and use that for results like the third pic here using the red-green default gradient to build a colour palette that looks like the one used in the movie Amelie.