Much prior to that the Sahara desert was a populated grass land.
I think we need to give early man more credit. (Maybe if they were as stupid and lazy as some of us are now, we wouldn't exist.) I believe that early man migrated far more than what we think. In a mobile society, of coarse you would move if conditions became adverse. (And heck, no government to demand they fix it.)
1,000 years = about 50 generations is plenty of time for groups to make a move to "greener pastures" as would be the want of hunter/gatherer societies.
Mankind, bless 'em, has always wondered what lay over that next mountian. The frightened, weak, slow hairless ape forced to use his wits to survive in a world ruled by tooth and claw managed to come out of Africa and walk the moon in something like 5,000 generations.