"They were arguing that because the earliest forms of this particular genetic sequence in living people was found in Africa, that meant that all people must have come from Africa.
The Australian National University team looked at the DNA found in the mitochondria of these ancient people's cells. mtDNA, as it is known, is inherited only from females and also mutates - errors appear - at a steady rate, meaning it can be used as a "molecular clock" to investigate human history.
But the Australian researchers contend that the DNA sequences isolated from Mungo Man's bones show him to have a genetic lineage that is both older and distinct from this line.
Given the undoubted modern appearance of Mungo Man, they argue, major doubt must now be cast on the so-called "Out of Africa" hypothesis in which all living people are said to be descended from a group of modern humans who left their African homeland no earlier than about 120,000 years ago.
Alternative explanation
"What our evidence shows is that the situation is much more complicated than any of these supporters of Out of Africa would have imagined," lead researcher Dr Alan Thorne said.
"They were arguing that because the earliest forms of this particular genetic sequence in living people was found in Africa, that meant that all people must have come from Africa.
"Well, logically, that's not true anymore because we now have an older form of indisputably modern human that comes out of Australia."
Dr Thorne, whose team have published their research in the Proceedings of the National Academy of Sciences, is a proponent of the alternative, multi-regional explanation for the emergence of modern humans.
This suggests that modern humans arose simultaneously in Africa, Europe and Asia from one of our predecessors, Homo erectus, who left Africa more that 1.5 million years ago.
"Modern humans didn't just come from one area, they came from all areas," Dr Thorne said. "We assert that when people began to leave Africa about two million years ago, they were the ancestors of all modern people and we don't think modern humanity emerged from one place later on.
European studies
"We simply say that here we have a form much older than anything found in Africa and there's no evidence that it, or the skeletal anatomy of the fossil that it comes from, ever had anything to do with Africa. In fact, the skeleton looks very much like slightly earlier fossils that we know were in China."
But Out of Africa supporters are not about to let go of their beliefs because of the Australian research. Professor Chris Stringer, from the Natural History Museum in London, UK, said that, given experience with European fossils, there was some doubt over whether DNA analysis of such old samples was reliable. And he said the research community would want to see the work repeated in other labs before major conclusions were drawn from the Australian research.
But even assuming the DNA sequences were correct, Professor Stringer said it could just mean that there was much more genetic diversity in the past than was previously realised.
"There is no evidence here that the ancestry of these Australian fossils goes back a million or two million years, which is the multi-regional prediction."