Humanoids of some kind. 250,000 years is probably the oldest more or less modern man, and 40,000 years is the beginning of modern man. Roughly speaking.
I think 125,000 years old is the oldest estimate I've seen for the age of Modern Humans...with an exit from Africa about 90,000 years ago. Albeit, I have some strong suspicions that some of these early folks (see post # 8) may have became modern somewhere outside Africa.