Correct answer: Until they cannot interbreed any more...
By that standard, lions and tigers are the same species.
The actual standard used these days, is that a population or organism needs to be a monophyletic lineage with a significant degree of genetic divergence from the next most closely related monophyletic lineage.
It will all depend on what the selective pressures are. If the new world is not all that different from the old one, or technological adaptation nullifies selective pressures from the environment leaving you only with genetic drift and sexual selection... give it a few hundreds of thousands of years.
H. Neanderthal is usually said to have arisen about 600,000 years ago. H. sapiens about 100,000 to 200,000 years ago. They are considered separate species, and while interbreeding may have occurred it was a rare thing, at least as far as leaving kids behind. So, no, you don't need millions of years, but you do seem to need a time span in the six digits of years.
Except that H. Sapiens did not diverge from H. Neanderthalis. Both diverged from H. Heidelbergensis. But yes, six digit years.
There's also some amateur eugenics going on, with the "unfit" being weeded out (not exterminated, just encouraged not to breed,for the good of the species.
How much of an effect might that have?
It depends on what is considered "Unfit".
As for the neanderthal/sapien thing, they're considered different species because of their different morphology. We were apparently able to interbreed with them, as (according to a fairly recent study, dumbed down here in a Scientific American article) apparently a few percent of the DNA of non-Africans comes from our H.neanderthalensis ancestors. It could be argued that we aren't separate species at all, but different subspecies of H.sapiens.
And that argument would be wrong because the Biological Species Concept is dead. If we accepted that standard, most of the world's couple thousands of species of toads would be the same species, irrespective of whether or not they diverged from the same common fucking ancestor.
The problem with modern humans is that not only are we incredible adaptable from a biological standpoint, but how powerful our technology is. The fact that we can use tools to alleviate environmental discomforts immensely reduces the impact of selective pressure.
No. It does not. It just shifts it from morphological adaptation to selection for social traits, behaviors, and cognitive processing.
God I love it when lay-people talk about evolution. It is like lapping up the years of orphaned gypsy children.
Warning, latin butchering ahead:
Genus Species Subspecies
Homo sapiens sapiens <- our subspecies
Homo sapiens novus <- their subspecies (The New Homo sapiens, masculine, nominative, singular)
Homo sapiens centauri <- perhaps the Alpha Centarians (masculine,genitive)