Svante Paabo assumes "some new creature" "carried this mitochondrial genome out of Africa about a million years", as do most commentators. It strikes me that a multiregionalist explanation is as consistent if not more consistent with the evidence at hand. If we entertain the possibility that "African Eve" ultimately descends from Eurasian Homo erectus, we don't need to posit some unknown intermediate "out of Africa" event.
Reference: Johannes Krause, Qiaomei Fu, Jeffrey M. Good, Bence Viola, Michael V. Shunkov, Anatoli P. Derevianko & Svante Pääbo. The complete mitochondrial DNA genome of an unknown hominin from southern Siberia. Nature advance online publication 24 March 2010. doi:10.1038/nature08976.