I've planted trees as the ground was just starting to thaw and some snow was around. I think they'd've grown just fine if I had protected them from the deer
Silly question, but are you sure the ground is frozen under the snow? I just went out to my field the other day, scraped aside 8" of snow and the ground wasn't frozen despite lows in the negative teens a week or two earlier.