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.

One of my favorite little tricks is something that was added in Photoshop 5.5 for Windows, 6 for Mac. It's under the Adjustments sub-menu (you know, where the Levels are located?). It's further down this list...

This one's called Gradient Map. What it does is more or less the same thing as the GIF color tables, except that it's not limited to 256 colors. It converts the image's luminosity, which ranges from 0 (black) to 255 (white), to whichever gradient you choose or design - and applies it over the entire image. What this means is if your gradient ranges from black to white, the result will be a grayscale image.

What's more interesting is if you try it with some actual color...so I've attached an image with some various gradient maps applied...the first is black to white. The next is the same black to white with a hazy, muddy blue stop added at 50%. The next is the chrome gradient, which ships with Photoshop. The last is a different kind of gradient, a Noise rather than a Solid gradient which works a little strangely, but if you play with it, you'll understand what it does.

The way you actually USE the Gradient map is as such:

Go to your Image menu, follow down to the Adjustments submenu (second one down). In the Adjustment menu, near the bottom, select 'Gradient Map...'

When the Gradient Map dialog opens, your image instantly changes reflecting a preview of the gradient displayed (if you don't play with gradients often, it's set by default to 'foreground to background.' If the foreground to background colors aren't at their defaults, your image WILL look wierd.). Click on the gradient itself to bring up the gradient editing dialog, the preview will continue to reflect the gradient as you edit it.

I won't go into how to use the editing dialog here because, firstly - it's pretty self evident if you're familiar with Photoshop and secondly - this is getting to be kind of long as far as add-ons go. However, if anyone has any questions, post a reply or email me at my renderosity address (i.e. click on my name and send an email).

Anyone able to stump me with a Photoshop question gets a pizza.

Hey, the Pizza thing goes for me too, provided you're not talking about anything specific to over 5.5 which is all I have (and, really, all I need) One note of major difference between Trick's technique and mine is that his works to totally change the colour scheme, while mine does it subtly. Before the Gradient Map tool you could get largely the same effect by a technique similar to mine above, except the difference is you would convert to Indexed Colour using a set number of colours -- say, 32. Then you would load up a colour table with that many colours arranged in the right order and all and replace the colour map, then continue on as before with my technique. The one I listed, however, takes advantage of the fact that Photoshop will try to dither a set colour map to match as closely as possible on conversion -- this makes the end result look very similar to the original within the realm of what colours are possible with the limited palette.

OK, for 5.5 and below Dodger's technique is the better technique, and he makes a good point. My technique does change the entire spectrum. There is one other feature, which cancels this out and adds the Gradient Map as a more subtle effect, or more pronounced depending on how you use it. They're called Adjustment Layers and they can be accessed either by using the little button on the layer palette that looks like a half-moon (it's a pop-up menu), or through the Layer menu, under the Add>/Add Adjustment>/whatever submenu happens to have them (they appear in several areas, increasingly so in later versions...7 makes them available in five locations). Anyway, applying the Gradient map in this fashion opens the possibility of bledning modes and opacity settings being applied to the effect...plus the whole slew of layer effects and layer masks. This does, however, take more time and Dodger's technique is far and away the faster and simpler of the two. However, one of the inherent beuties of Photoshop is that there are usually 5 or 6 different ways to approach any problem, and none of them is neccessarily better than another.

Yup. Like, for instance, instead of an adjustment layer, you could copy the layer you want to effect (or select all, copy merged, and paste, if you're working with multiple layers) and then change the merge mode of the new layer to colour and adjust the opacity, or play with other merge modes.