Replacing a Dull Sky in Photoshop Elements

The majority of our work is done and we could stop here but there are some things I don't like about the image as it is now. For one thing, there are some obvious fringe pixels that don't blend well around the dark hair on the two people on the right. Also the sky darkens the picture too much and overall it just looks faked. Let's see what we can do to make it better...