Are you working with something already shot or are you trying to create this effect from scratch?

If already shot and you have a clean skyline and the object that you want to remain at normal speed is below this skyline you could try masking out the sky with the bezier mask tool. Then add the clip again as another track and speed it up. This would show through where the sky is masked out in your normal speed track.

I guess it would have to be a steady shot as well. Any panning or zooming would make this alot more difficult if not impossible.

You need to learn about 'Chroma-keying'. First you get footage of the sky. You speed it up using the 'Time-stretch' feature of Vegas. (You click on the video of the sky and hold it down and then you push your Ctrl button. A wavy line will appear under your Icon. Then push the video track in on itself to make it smaller. This speeds it up. Now watch it. If not fast enough, Render it to a new AVI then take that new AVI and 'Time-stretch' it again. Remember each time you do this, it gets shorter and shorter. When it looks right save it.) Now you need to learn 'Chroma-keying'. This is when you use a Green or Blue tarp as a back drop and put your actors or subject in front of this 'tarp' or whatever, and have them perform or do whatever you want them to do. (you will need some practice to perfect this) When you do your final render, one video track will have your Clouds scene and the track above it will have your actors in front of the 'tarp' or colored wall and then when you apply the 'Chroma-key' effect, it will delete the colored wall or tarp and leave the actors standing in front of the fast moving clouds. (the real trick to this, is getting your tarp or colored wall to be exactly one shade and not get any shadows on it. Lighting and the right shade of color are really important. It will look cool in the end. A lot of work though.

Actually this is pretty easy to do, I think.
Firstly shoot the foregorund scene with a clear, even sky at normal speed.
Now shoot your 'ominous' sky. If you can shoot it from the same camera position so much the better but not vital, just so long as the sky you're going to use has the same perspective.

Now speed up the 'ominous' sky and render out as new clip. (Yeah I know this isn't necessary but saves confussion)

Now put first clip on top track, sped up sky on second track and apply chroma key using sky on first track. Don't panic if the key isn't 100 perfect! You can always render out the mask and then add or subtract to/from it using another track of generated media. Then use your mask to composite the two tracks rather than the CC FX. This should work OK even if you've got a pan except you'll need to do a very slow pan on the sky that you're going to speed up so that when it's sped up the rates match, tricky but not impossible. One solution might be to shoot lots of still with a high res still camera so you can pan withing them and still have adequate resolution.

The trick to many effects is planning before you start!

Bob.

Vegas also includes a cloudy sky media and another you can build to suit. You can pan to make the clouds move.

When I first met my wife the earth and sky moved....

One thing that will help get a better sky is to use a poliarized filter.
This will bring out the blue.