In Death and the Penguin, Misha non-Penguin left New Year's Presents (from "Grandfather Frost") under their tree. I'm slightly confused by this; was Christmas not celebrated at this point? If not, was this a carryover from the Soviet era? (The book is definitely set in post-Soviet Ukraine).
Yes, this is a carryover from the Soviet era, Julian calendar notwithstanding.
A new ideology or religion has better chances of retaining and claiming new adherents by assimilating old well-established traditions rather than fighting them. Like the Christians before them, communists (after a brief period of revolutionary rejection) moved to adopt some of the most established traditions, including Christmas celebration.
Of course, it was to be devoid of any religions meaning. But there must be some meaning, and celebrating the New Year was the obvious choice. (There was a distinct lack of a major 'civil' festival, given the already established Labour and Revolution days).
The change happened in the late 1920s, so for many generations of Soviet citizens the New Year came to be the main winter (and civil) celebration; even the main celebration of the year. Superficially, most of the rituals were retained from Christmas: the tree, the presents, "Grandfather Frost" ('Santa Claus')...
So, when the 'real' Christmas was back on the agenda in the 90s, this caused confusion. And the New Year tradition was so strong and so much loved that it still dominates Christmas (in Ukraine and Russia) for most people.
The Julian calendar (celebrating Christmas on the 7th Jan rather than 25th Dec) is rather a hindrance for celebrating the New Year: the week before Christmas is fasting, whereas New Year is most famous for its midnight feast. The more religious Orthodox people tend to celebrate the 'old' (Julian) New Year on the 14th Jan. Those who celebrate the 'normal' New Year just can't be counted as true Orthodox. Yet not celebrating it was almost unthinkable...
So, in summary, there is still unresolved confusion about all these old/new year and Gregorian/Julian Christmas: they are somewhat mutually exclusive. But for the older (i.e. ex-Soviet) and non-religious people (i.e.: most people), New Year still is the main celebration of them; the tree is usually called "New Year tree" rather than "Christmas tree", etc. Most likely Misha either didn't celebrate Christmas, or didn't take it seriously enough.
Ukraine, like many Orthodox countries, celebrates Christmas on 7 January rather than 25 December, as they still follow the Julian calendar for religious holidays. It's only recently that there's been any discussion of transitioning to a 25 December celebration (25 December became a Ukrainian public holiday in 2017).
Presents are therefore left under a "New Year tree" rather than a Christmas tree:
New Year's Day is one of Ukraine's favorite holidays. On Christmas Eve, Ukrainians exchange gifts, and children receive their presents under the New Year Tree on the morning of January 1. The week before New Year's is a time for shopping, parties at work, decorating fir-trees, and cooking special meals. The main folk heroes of this holiday are Father Frost (Did Moroz) and his grand-daughter "Sniguron'ka" (The Snow Girl). The tradition of predicting fortunes on this night is very popular among young people.