The upshot of this Malyarchuk et al. article, published in PLoS One today, is that mitochondrial haplogroup U5 originated somewhere around the Mediterranean 25,000 to 30,000 years ago. It was then taken east via Central Europe, most likely as things warmed up following the Ice Age (LGM). Also, the authors suggest that pre-LGM Eastern Europeans carried U2, citing the recent discovery of this marker in Upper Paleolithic remains from Kostenki, Russia.
Genetic data obtained in this study allows the suggestion that during the LGM period, central European territories probably represented the area of intermingling between human flow from refugial zones in the Balkans, the Mediterranean coastline and the Pyrenees, as U5a and U5b gene flows occurred from there. Based on dating analysis of the U5 subclusters, it seems very likely that, despite the archaeological evidence testifying to the presence of humans in eastern Europe during the Ice Age, this part of Eurasia might have only been re-populated by modern humans at the end of the LGM, i.e. later than central Europe. In addition, U5b gene flow from central to eastern Europe become much more intense after the LGM.
It's impressive how far east this putatively Central European gene flow pushed, with traces of it popping up in modern Tatar and Siberian groups. This illustrates how Europe was not only a destination for migrants, but also potentially a major migrant source, particularly to the steppe and forest-steppe zones of Asia.
Subcluster U5a1d has been detected in eastern Europe (in Russians, Belorussians and Tatars) and southern Siberia (in Buryats) (Figure 1, Figure S1). The presence of such old U5a1 lineages in eastern part of Europe may be indicative of eastern European origin of the whole U5a1 subcluster, however ancestral haplotype for U5a1 has been found in central Europe in Czechs (Figure 1).
A recent ancient DNA study of Stone Age hunter-gatherers from central and eastern Europe has shown that most of the samples studied (.80%) shared mtDNA haplotypes belonging to haplogroups U5 and U4, haplogroups that notably are relatively rare in central Europe today . Among them, sample 5830a from Hohlenstein-Stadel (Germany), defined as U5a2a, based on the HVS I sequence 16114A 16192-16256-16294-16311, was detected. Its closest HVS I relatives in modern populations can be found among eastern Europeans (in Latvians, Russians, Tatars and Mordvins).
But despite the fact that U5 seems to have originated around the Mediterranean, it's now most often found in Northeastern Europe. What appears to have happened is that when frequencies of mtDNA U dropped like a stone across much of Europe, probably during the Neolithic transition, the northeast was less affected by these changes. This possibly indicates that today the populations with the most sizeable amount of indigenous European hunter-gatherer ancestry live on the eastern shores of the Baltic. This view is seemingly backed up by genome-wide studies, which show Baltic and Balto-Finnic groups as the most distant genetically from modern-day Southern Europeans, who likely are of overwhelmingly Near Eastern Neolithic farmer origin (for example, see here).
Malyarchuk B, Derenko M, Grzybowski T, Perkova M, Rogalla U, et al. (2010) The Peopling of Europe from the Mitochondrial Haplogroup U5 Perspective. PLoS ONE 5(4): e10285. doi:10.1371/journal.pone.0010285