Two years ago, in September 2013, cavers went deep into the Rising Star cave in South Africa. They found fossils of a previously undiscovered ancestor of humans. The new species, Homo naledi, fits into a fossil gap between the Australopithecine, and Homo erectus. The followup expedition found more bone fossils than at any other pre-human site in Africa. They found bones from at least 15 individuals.
Many of the features fell between what you would expect for Australopithecus and Homo: teeth, pelvis, hands, etc. The skulls looked like Homo, but the brain case was a little of half the size of H. erectus’s.
It is difficult to determine how old the fossils are. They weren’t found embedded in rock, which would allow radiometric dating, and are too old for carbon dating. If H. naledi is very old, it could predate Lucy; if young, it would be contemporary with H. erectus. But most likely is that it would fit in just as the Australopithecines and Homo branched, around 2,000,000 years ago.