Hi Asikes,
At least you recognized the fact that a nice sky would really make the shot look a lot better. I see so many posts where they just leave the blown out sky and the question is about something else in the shot.
A gradiant will be really hard because of the leaves, whether you are masking or erasing the leaves are just going to be a pain in the butt. I did this with one click. I use PSP and it has a tool called color changer. One click and it filled in the sky. I also took out the half way house bottom left. Just looked funny with half of it there and the other half blown out.
You say you are using PS which I assume is Photoshop but I know a lot of people who say that are really using Elements. Not knowing exactly what you are using, I can only give you a general guideline to find the equivelent of the Color Changer.
Hope that helps.
LaDair