OK... I did a little 5 minute go at this. If I spent a little more time I'm sure I'd have it better, but this should get you on the way.
Forget the threshold because it didn't really work on this, but the curve technique did wonders.
I used the blue channel (as this had the most contrast) for the mask. I copied it and then ran a curves adjustment to pull the blacks down. I clicked the white eye dropper and clicked on the sky to lift it completely to white. Taking your time on this bit (which I didn't) will get it spot on.
Then I painted black all over the bottom part of the image.
Back to the RGB channel mode and then on with the rest.
Load the mask you've just created (I called mine 'Alpha')
Right... this bit I led you astray... hold down ALT when you click the mask button (this is the same as clicking the mask button and then pressing CTRL-I by the way).
Put your new sky on a new layer underneath your photo.
Hopefully you should now have a nice new sky.
If you see a bit of your old sky or white/grey fringing (like in mine), then simply click on the mask and either run your curves again, or what also works is very slightly running a gaussian blur on your mask.
Remember the mask is the key to this method.
Use the best tool in your arsenal to help you... your eyes.
Hope this helps matey!