While I agree with Dirtmechanic that the trees put the leaves where they will do the most good, and we should appreciate them where they lie... Personally I wouldn't expect the soil to stay completely unfrozen.
That isn't how insulation works.
What the leaves do is keep the soil frozen after it eventually does freeze, and this prevents frost heave... which can do some damage...
insulation levels out the temps that the plants have to deal with.
too much up and down of temps can stress the plants.
And...
The leaves on top of the soil should help prevent a really deep freeze...
Maybe try an auger to compare depth of frozen soil?