Well he'd have been 'thawing out' on the way down, but that's not very much.
Assuming he was only say a thousand metres up when they opened the wheel bays and he fell out, he'd have been dropping for roughly a minute (1000m at 120MPH, roughly terminal velocity for a human sized & shaped object). That's not a lot of defrosting time in the fall, even with the heat created by friction. You could alternatly assume he'd been thawing out since the plane started to descend, which could be 10 or 15 minutes or so. Still not very long really if he was supposedly frozen solid.
Given he didn't hit the street like a cannon ball you'd have to assume he wasn't solid when he hit the ground. Or there'd be a big hole as well as bits all over the place.
Indeed. Mythbusters should drop a mannequin filled with frozen chicken breasts out of a helicopter at 1000 feet, see how defrosted they are when they pick up the bits on the ground...
Jon