Another way to deal with this is to use a 16 point garbage matte and a picture of a blue sky with some wispy clouds. Since the garbage matte can be animated, it is OK if there is some movement.
If there is way too much movement to deal with mattes or gradients, it might be appropriate to use a color replacement.
This is a complete over exageration, but this is the result of a simple "Change to Color" effect. The settings for this are shown below. I simply used the eyedropper to pick a part of the sky and then selected a nice blue to change it to. As I said, I overdid it on purpose so that it would show up better. I could have used the eyedropper to select a part of a real sky that happened to be close to what I wanted. I put the clip on track one and a copy on track two. I cropped the upper track to provide a split screen. I could also have used calculations to blend the two.