Let me enter the following points which might be very relevant to the finding that in North Africa: "the Neandertal's genetic signal is higher in populations with a local, pre-Neolithic North African ancestry".
First of all, this is unexpected if Neandertal admixture took place in the Near East; if that were the case, then Near Eastern back-migrants would be more Neandertal-like than aboriginal Homo sapiens that had not participated in the Out-of-Africa event.
Second, I have followed up on John Hawks' suggestion that UP Europeans were more Neandertal-admixed than current Europeans, and using Oetzi's genome, discovered that potentially this is true. This is also unexpected if admixture with Neandertals took place in the Near East.
A link between aboriginal North Africans and UP Europeans of course exists: relationships between the Mechta-Afalou and Cro-Magnoids have long been recognized in physical anthropology.
An even more remote link involves Jebel Irhoud 1, the first modern human whose skull we possess from North Africa. Not only were the associated industries Mousterian (same as European Neandertals), but the skull itself was originally considered to be an African Neandertal, before it was reclassified as a member of H. sapiens.
I will update this entry after reading the paper with any further observations.
PLoS ONE 7(10): e47765. doi:10.1371/journal.pone.0047765
North African Populations Carry the Signature of Admixture with Neandertals
Federico Sánchez-Quinto et al.
One of the main findings derived from the analysis of the Neandertal genome was the evidence for admixture between Neandertals and non-African modern humans. An alternative scenario is that the ancestral population of non-Africans was closer to Neandertals than to Africans because of ancient population substructure. Thus, the study of North African populations is crucial for testing both hypotheses. We analyzed a total of 780,000 SNPs in 125 individuals representing seven different North African locations and searched for their ancestral/derived state in comparison to different human populations and Neandertals. We found that North African populations have a significant excess of derived alleles shared with Neandertals, when compared to sub-Saharan Africans. This excess is similar to that found in non-African humans, a fact that can be interpreted as a sign of Neandertal admixture. Furthermore, the Neandertal's genetic signal is higher in populations with a local, pre-Neolithic North African ancestry. Therefore, the detected ancient admixture is not due to recent Near Eastern or European migrations. Sub-Saharan populations are the only ones not affected by the admixture event with Neandertals.