The paper echoes many of my criticisms about the theory which I expressed here and here.
The authors put it quite succinctly what was expected of the Neandertal genome by the two competing theories (Out-of-Africa vs. multi-regional) that stand on opposite ends of the spectrum:
There are two predominant models of modern human origins: multiregional evolution and recent African replacement. Multiregional evolution posits that the evolution of contemporary peoples occurred around the globe, with archaic populations such as the Neandertals contributing locally in their geographic regions . This model predicts that Neandertals will share significant genetic variation with Europeans to the exclusion of other populations. Recent African replacement suggests that contemporary humans owe their heritage to a small African population that spread around the world replacing archaic populations with little to no interbreeding . This model predicts that Neandertals will be equally distantly related to all contemporary human populations.The surprising find about the Neandertal genome is that they were more closely related to Eurasians than to Africans (Yoruba and San): this conflicts with both models. The authors of the original study saw two ways out of this:
First, that humans absorbed Neandertal genes in the Levant that somehow managed to get distributed evenly across Eurasia, to the extent that a Papuan is as close to Neandertals as a European is, even though there is no hint of Neandertal presence in Papua or thousands of km close to it.
Second, that there was African population structure, and that Neandertals and modern humans formed a clade with respect to other African hominids. The breakdown of this structure drove some Africans away from Neandertals, rather than Neandertal admixture in Eurasians driving them towards Neandertals.
The authors of the current paper propose that:
We propose a third alternative. The paleontological and archaeological records suggest that modern humans and Neandertals overlapped in the Eastern Mediterranean region around 100 thousand years ago during a time when the African faunal zone extended temporarily into the Middle East. The range of modern humans then likely contracted back into Africa, severing contact with Neandertals, before finally expanding their range out of Africa around 50 thousand years ago . Admixture may not have been possible during this time because a southern route out of Africa through the Arabian peninsula  would not have put the populations in contact. Any admixture would have occurred prior to the expansion of modern humans out of Africa between East Africans and Neandertals (Figure 1C). If this is correct, Neandertal genes will be found at low frequency in East Africans and perhaps others. These low-frequency Neandertal genes may then have been pushed to high frequency or fixation in the out of Africa populations through the iterated founder effect associated with range expansions .The authors call (like I did) for sampling East Africans for evidence of "Neandertal genes".
Of course East African-Neandertal admixture prior to the Eurasian expansion would have the desired effect, the same as my favored model of deep African population structure.
But, a new curveball was thrown our way by the discovery of 100ky anatomically modern humans in south China. The third alternative seems less plausible now: it would be possible to think of modern (Neandertal-admixed) humans retreating back to east Africa after 100ky due to a retreat of African fauna from the Middle East when we didn't know about the Chinese modern Homo sapiens. But, now, we have to conclude that there were modern humans living between Israel and south China 100ky ago, and any idea of retreat becomes implausible.
Thus, I still believe that the 2nd scenario (deep African population structure + common Neandertal-sapiens ancestor in East Africa) is more plausible.
Nonetheless I, like the authors, have arrived -for different reasons- at the same conclusion: east Africans need to be sampled for Neandertal genes.
If humans admixed with Neandertals in Eurasia, then we expect East Africans to have Neandertal genes in proportion to their Eurasian admixture. Let's say 4% Neandertal genes and 10% Eurasian admixture in a particular east African population. Then, we expect about 0.4% Neandertal genes in this population. If we find much more, then there will be something wrong with the theory of "Neandertal admixture in Eurasia".
Current Biology Volume 20, Issue 12, 22 June 2010, Pages R517-R519
Neandertal Genome: The Ins and Outs of African Genetic Diversity
Jason A. Hodgsona, Christina M. Bergeya and Todd R. Disotell
Analysis of the Neandertal genome indicates gene flow between Neandertals and modern humans of Eurasia but not Africa. This surprising result is difficult to reconcile with current models of human origins and might have to do with insufficient African sampling.