The genetic model of the "Out of Africa" scenario is getting more complex. There may be two waves, as well as the likelihood of admixture between the Neo-Africans and "archaic" hominins, such the Neandertals and Denisovans. From what I can gather the genetic evidence is now converging upon the sequence of events where African populations diverge >100,000 years ago (e.g., a deep separation between the ancestors of the Bushmen and the ancestors of West Africans), and a radiation of non-Africans at most ~75,000 years ago, and more likely ~50,000 years ago. There are still many holes to be plugged in. While we're waiting on genetics, here's an interesting paper using archaeological methods in PLoS ONE, The Nubian Complex of Dhofar, Oman: An African Middle Stone Age Industry in Southern Arabia:
Despite the numerous studies proposing early human population expansions from Africa into Arabia during the Late Pleistocene, no archaeological sites have yet been discovered in Arabia that resemble a specific African industry, which would indicate demographic exchange across the Red Sea. Here we report the discovery of a buried site and more than 100 new surface scatters in the Dhofar region of Oman belonging to a regionally-specific African lithic industry - the late Nubian Complex - known previously only from the northeast and Horn of Africa during Marine Isotope Stage 5, ~128,000 to 74,000 years ago. Two optically stimulated luminescence age estimates from the open-air site of Aybut Al Auwal in Oman place the Arabian Nubian Complex at ~106,000 years ago, providing archaeological evidence for the presence of a distinct northeast African Middle Stone Age technocomplex in southern Arabia sometime in the first half of Marine Isotope Stage 5
Dienekes has extensive commentary up.