Sparsely sampled distributions will necessarily have tails that are not represented in the sampled data, and for early humans those tails could plausibly go back much, much further than the current record shows.
As such, we can expect that there will be a slow, steady stream of "surprising" early finds that push back hominid evolution to much longer ago than previously appreciated. The same is true of dinosaurs or any other species: the rarity of fossilization events is such that the probability of the earliest surviving fossil being particularly close to the emergence of the species is just not that high.
It would be interesting to do a serious analysis of the fossil discovery distribution to see if we can make a better estimate of the earliest emergence of hominids based on empirical estimates of fossilization and discovery probabilities.