Here's my version.
I guess it's a matter of selecting the sky properly.
1) Select/colour range (Use add samples and click on various part of the sky to make sure the different shades of colours in the sky are selected. Adjust the fuziness so that the selected area would include all the sky but exclude most of the others. I used about 100 for fuziness in this case)
2) Lasso tool to fine tune the selected area (mainly to exclude the unwanted land area and trees)
3) Magic wand to fine tune the selected area (use exclude so that the edges of trees are deselected. Use tolerence levels approppriate to the situation)
4) Layer/New/Layer via copy (a new layer will be created with just only the selected area i.e. sky)
5) Click onto the new layer in the layer palette so that only it is selected.
6) lock the transparent area by clicking onto the relevant lock icon in the layer palette.
7) Use gradient tool (foreground to background, opacity 100%. Use gradient editor to get the colour and changes of shades you desire)
When the orignal background and the new layer is combined, it's done.