There is actually a discipline that studies this (theoretical anthropogeny) but it doesn’t seem to have come to any conclusions:
I [Ajit Varki] personally favor ~100,000 years ago, for several reasons. First, most current genetic data point to a common origin of current humans at about that time. Second, the humans who entered the Eastern Mediterranean (the Levant) at that time were burying their dead with funerary items, and transporting perforated shell beads (presumably made into necklaces) over rather long distances. Third, my group’s work suggests a population bottleneck caused by infectious disease just before that time. Finally, despite evidence for cross-fertility with other ancient hominins (including some in Africa), we BMHs [behaviourally modern humans] remained largely genetically distinct, despite tens of thousands of years of opportunity to mate and mingle into a distinct hybrid species in each locale. While this outcome could have been due to chance, I think it more likely that the initial hybrids were lacking a fully human-like theory of mind, and that the “cognitively sterile” hybrids could not easily incorporate themselves (or their genes) back into the BMH population.
Interestingly, the answers to an anonymous poll of the same faculty and students varied widely among the five possible time periods and populations I suggested (ranging from ~60,000 to ~500,000 years ago), with some respondents including Neanderthals as being equivalent to BMHs. So, even among experts and bright students who had just heard the latest research reports, there was no consensus on this issue. Much more data from many disciplines are required before there is any hope of finding the answer. (The Scientist )
Varki offers some interesting thought experiments though.
See also:
Neanderthal virus turns up in modern humans with cancer
A new study on early human dentition which suggested that no known hominin is a common ancestor of Neanderthals and modern humans.
Mystery human species “unearthed” from genome map of early humans? Despite such evident fertility, this is supposed to be a separate species?