Step 4 - Isolate your buildingsNow you get to choose which buildings you want to apply the effect to. First, you are going to want to select the city instead of the sky, so go to Select > Inverse, and then take the marquee tool "m" and choose the buildings that you want. Hold down option when you click and drag (this will get rid of the selected city on either side of your buildings. You should arrive at something that looks like the following image.
Step 5 - Prepping for a new skyWith these buildings selected, copy them (control/command + c) and paste them into a new layer, right where they were before (nothing should look different, you've only moved the buildings to a different layer). Name this layer "buildings". Now, in the layers palette, select the layer "buildings" (control/command + click on the layer "buildings"), and then turn of the visibility of the "buildings" layer, so you can see what you're doing. Now go back to the "city" layer (which now is without the buildings that you moved). Then, fill the selection with the color of the sky (use the eye dropper tool "i" to select a blue color somewhere in the sky, and then, fill the selection with the paint bucket/fill tool "g"). You should come up with something like this. Note: If you cannot seem to select the layer by clicking on it, you are probably clicking the wrong thing. To the left of the layer name, there is a small icon of the layer. You should control/command + click on that image, not the text itself.
Step 6 - Add a new sky (part 1)Now, select all the blue like you did before with the wand/quick select "w" tool. With this new selection, create a new layer (Layer > New > Layer) and fill it "g" with a brown (I used #5e5139). You should now see something like this.
Step 7 - Add a new sky (part 2)
Now we are going to add clouds. In a new layer, using a brown foreground and a black background, go to Filter > Render > Clouds. Once you've done that, hit control/command + T, and drag out the sides of the box so that the clouds get a little flatter, and stretched out looking. At this point, you should only see clouds. Take the eraser (using a brush size of about 300px, hardness of 0) and start erasing the bottom of the clouds layer, so that you can begin to see your city again. Customize this as much as you'd like. You probably want to see most of the buildings though. This is what my result looked like. Don't worry if your colors are a little off, we will fix that in the last step.