All Dave said is true, I second that. However since you’re probably stuck with the shot, here’s what I would do: definitely not a sky replace (it would be a lot of work for a not so great result). I presume you have the palm trees masked out. If so, duplicate the footage, apply mask on the top layer(so that you see the street and trees only) and color correct the layer below for the sky. There’s a number of ways to go based on how much info is in your source footage, but from the looks of it I would try to tint it blue and see if I can bring in more mid tones. So basically a color correction job (I highly recommend Magic Bullet Colorista)
Tudor “Ted” Jelescu
Senior VFX Artist
Bucharest, Romania
http://www.ennstudio.ro