I would suggest dealing with this as two parts – a key to remove the sky, and masks to remove the trees. Bear in mind that, since leaves are a somewhat reflective surface, you are going to hit the wall that’s based on the fact that some of the leaves are reflecting the sky. You will have to do a spill suppression as part of the key, so that the sky color is removed, replaced, or at least reduced. Otherwise, the cutout is never going be believable.
I’ve run into this doing broadcast TV work, creating scenes for the weather system, in which the sky would be replaced into an alpha mask created around the buildings/trees, and other objects. It always worked when there were just buildings (with some color correction), but hardly ever worked when there were trees and bushes, because even when you color correct them, each individual weather system sky was a different color temperature, depending on the weather (stormy, sunny, overcast, etc.). You always had to match the foreground to the background, to a certain degree, which sort of precludes automation.
Joe Bourke
Owner/Creative Director
Bourke Media
http://www.bourkemedia.com