The other option to fix the sky in Photoshop is by using a stock image of a sky. You can download one here (right click on the link and select Save target as...).

Now first save the Photoshop PSD file that you're working on for this tutorial.

Open the image of the sky, select the Move Tool in your tool bar, hold down the Shift key (this will center the image after we've copied it) and click on the sky image, hold down the left mouse button, move your cursor to the document you're working on and release the mouse button and release the shift key.

The sky image will now be a new layer in your layers palette, but of course it's too big which we're going to fix. With the Move Tool still active select in your option bar Show Bounding Box:

In Photoshop CS2 it's called Show Transform Controls.

Next go to the Navigator palette and enter a zoom value of 20%:

Note: if you can't find the navigator palette, select in the menu Window / Navigator (it will now have a in front of it)

Your document window should now look something like this:

Now hold the shift key and drag one of the corners inward to make the sky image smaller. If you have to move the image around then release the shift key and click inside the square, hold down the mouse button and move the selection. You can repeat those steps as much as you want, as long as you don't click on the red rotation point in the center of the transform box

Finally you should get something like this:

Notice that I made the box a little larger than the original canvas, which allows me later to move the sky slightly to the left or right if needed. Double click inside the box when you're done to resize the image.
Return to the option bar and deselect Show Bounding Box:
In Photoshop CS2 it's called Show Transform Controls.

Return to the Navigator palette and enter a zoom value of 100%:

Rename the layer to Sky - Stock Image by double clicking on its name.

Soon we're going to duplicate the mask that was added to the Blue Sky layer by copying it to the Sky - Stock Image layer (remember this important trick). Since Photoshop CS2 this is done differently than in older versions of Photoshop. Let's first have a look how to duplicate a mask in Photoshop CS2.

In Photoshop CS2 we can duplicate a mask by holding down the Alt key (Option key on the Mac), click on the mask and drag and drop it onto the target layer:

Notice that the layer Sky - Stock Image has to be the active layer (a double border around its thumbnail).
Photoshop CS2 users can now click here to continue with the next step.

Now let's see how we to duplicate a layer in older versions of Photoshop.
With the Sky - Stock Image layer still active (it will have a in front of it), click on the mask, hold down the mouse button, position your cursor on top of the Add layer mask icon and release the mouse button:

Now the layers palette looks like this:

The next step is to disable the link between the mask and the image it belongs to. You do this by clicking on the link symbol (marked with the red arrow) between the mask and the sky image. This will allow you to move the sky image upwards, without moving the mask. But first make sure that you make the sky image active by clicking on its thumbnail (A) in the layers palette, since we don't want to move the layer mask.

Now with the Move Tool still active, press the cursor up key on your keyboard to move the sky upward, until the bottom border of the sky is slightly below the horizon. You can speed things up by holding down the shift key while you're using the cursor up/down keys.

Here's the result:

 

I showed you how to replace the sky (because sometimes it's the best solution), but let's focus on the original sky to learn move about how to remove its noise. So for the sake of this tutorial make the Sky - Stock Image invisible by clicking on the eye icon in front of it but first lock the layer by clicking on the lock icon at the top of your layers palette (see next screenshot, A). The same icon will appear on the right of the layer's name.
Make the Blue Sky layer visible again and make it the active layer by clicking on its blue thumbnail in the layers palette (it will now have a icon in front of it):