I actually got a chance to play with this one. I didn't manage to make a colourful sky, but I tried my hand at making it more dramatic. What I did was:
Duplicated the background and set it to overlay. I changed this layer to black & white using the "Green Filter" setting for B&W in CS3 (I think that was the one).
Duplicated the background again and set it to multiply, which darkened the clouds and the whole picture.
Added 2 more layers using the Photo Filter adjustment. The first photo filter was "Deep Yellow" and the second was "Underwater".