I don't know if we should believe Svante Pääbo anymore, but his lab has some new findings re: Neandertal mtDNA:
Neanderthals in central Asia and Siberia
Nature advance online publication 30 September 2007. doi:10.1038/nature06193
Authors: Johannes Krause, Ludovic Orlando, David Serre, Bence Viola, Kay Prüfer, Michael P. Richards, Jean-Jacques Hublin, Catherine Hänni, Anatoly P. Derevianko & Svante Pääbo Morphological traits typical of Neanderthals began to appear in European hominids at least 400,000 years ago and about 150,000 years ago in western Asia. After their initial appearance, such traits increased in frequency and the extent to which they are expressed until they disappeared shortly after 30,000 years ago. However, because most fossil hominid remains are fragmentary, it can be difficult or impossible to determine unambiguously whether a fossil is of Neanderthal origin. This limits the ability to determine when and where Neanderthals lived. To determine how far to the east Neanderthals ranged, we determined mitochondrial DNA (mtDNA) sequences from hominid remains found in Uzbekistan and in the Altai region of southern Siberia. Here we show that the DNA sequences from these fossils fall within the European Neanderthal mtDNA variation. Thus, the geographic range of Neanderthals is likely to have extended at least 2,000 km further to the east than commonly assumed.