Oldest Ancient mtDNA From Modern Humans In Europe Found in Bulgaria

The oldest mtDNA of modern humans in Europe ever studied has been fond in a cave in Bulgaria dating to the early Upper Paleolithic era. 

These are very basal implying that mtDNA M, N and R started to diversify not very long (perhaps a few thousand years) before these individuals were born. These samples can be used to infer the date of the most recent common ancestor (TMRCA) in these clades in a manner less prone to systemic error than estimates based upon modern mtDNA samples where more mutations from the basal root have occurred. 

This also favors the development of mtDNA R (a branch of mtDNA N), and mtDNA U (a branch of mtDNA U) someplace further West than commonly assumed, and probably in common with or near the birthplace locations of mtDNA M and mtDNA N.

This tends to support the notion that the root of these mtDNA clades are close to the "late Out of Africa date" ca. 50,000 years ago, even though archaeological evidence establishes that there were earlier migrations of modern humans out of Africa, which presemably, that left no material impact on the modern gene pool due to extinction or population replacement of those earlier wave people and their descendants.

The Bacho Kiro cave is located 5km west of the town of Dryanovo in Bulgaria, on the northern slopes of the Balkan mountains and approximately 70 km south of the Danube. The interior deposits cover the end of the Middle Paleolithic and the beginning of the Upper Paleolithic.

Inside this cave, archaeologists have found a human molar (F6-620) whose anatomical characters are closer to those of modern men, than of Neanderthals, as well as six human bones determined by the analysis of their collagen. The direct dating carried out on these human vestiges gave a value ranging between 46,790 and 42,810 years. 

The authors analyzed the mitochondrial genome of the tooth and these six bones. The result showed that all of these remains belong to modern men. The tooth and one of the bones have the same haplotype which belongs to the base of haplogroup M with two additional mutations unknown in the different current branches of M. Two samples are located at the base of haplogroup N with also two additional mutations unknown until now. The closest identified haplotype of these two samples is that of Oase1. A bone has a haplotype that belongs to the base of haplogroup R without additional mutation. Finally, the last sample belongs to the U8 haplogroup previously identified in different Upper Paleolithic sites.

Thus, these human remains are the oldest remains of modern man in Europe. Estimating the age of these individuals based on their mitochondrial DNA calibrated by other former individuals, gives a value between 44,830 and 42,616 years, in good agreement with the dating estimated directly on the bones.

From Bernard's Blog (translation by Google). 

Razib Khan also discusses the papers. He notes that (in seeming partial contradiction to Bernard) that:

The results established that these individuals were basal non-Africans of haplogroup M. Today there are very few West Eurasians, and almost no native Europeans, who carry haplogroup M, which is frequent in India and parts east. But this is not the first M found in Europe during the Pleistocene. The point though is that in concert with the results for Oase in Romania roughly contemporaneous (if perhaps somewhat later), they establish strongly that the first modern humans in Europe did not leave descendants in the continent. . . . 

these results confirm that Neanderthals and modern humans existed in Europe for at least 7,000 years simultaneously. . . . The authors even suggest that Neanderthal archaeological cultures exhibit modern human influence. . . .  

One stylized fact that has long been fascinating is that Australia seems to have been occupied by modern humans 5-10,000 years earlier than Europe. A reasonable explanation for this fact is that Neanderthals occupied Europe. . . . Though there are older dates, very high confidence results indicate that humans reached Australia 49,000 years ago. This site would be only 2,000 years later, and it seems plausible that this wasn’t the first. 

The best genetic evidence now suggests that at minimum modern humans began to diversify 200,000 years ago in Africa, though it is more likely that some lineages branched out earlier. 

Among “non-Africans,” some groups may have separated earlier, the “Basal Eurasians” (they may have less Neanderthal than the other non-Africans). But the majority expanded explosively ~50,000 years ago. These are the ancestors of European Pleistocene and Mesolithic hunter-gatherers, and Oceanians, East Asians, and other eastern peoples.

I personally think that the influence on the Neanderthal culture may be due to admixture rather than pure cultural diffusion, based on the current evidence, although I'd be happy to change my mind in the fact of new data. Also, co-existing in Europe and co-existing in the same location are not necessarily the same thing. Locally (by definition) time periods of co-existence were shorter and a time frame of 1,000 years in any one place is not completely implausible.