The paleolithic is the time of the pre-historic hominid tool user. It begins 2.6 million years ago with Australopithecine-like hominid tool users and ends with the last ice age 8,000 years BCE .
The paleolithic is divided into three variably defined ranges, something like this: 
- Upper: 45,000 - 8000 BCE.
- Middle: 300,000 - 30,000 BCE
- Lower: 2.6 million to 100,000 BCE. (The great age of exploration, including, it seems, rafting .)
It's helpful to know this, because it's otherwise hard to understand what Caspari is saying in her recent SciAm article. She claims that humans had short lifespans throughout most of the paleolithic ...
... the Krapina Neandertals are not unique among early humans. The few other human fossil localities with large numbers of individuals preserved, such as the approximately 600,000-year-old Sima de los Huesos site in Atapuerca, Spain, show similar patterns. The Sima de los Huesos people had very high levels of juvenile and young adult mortality, with no one surviving past 35 and very few living even that long...
...We observed a small trend of increased longevity over time among all samples, but the difference between earlier humans and the modern humans of the Upper Paleolithic was a dramatic fivefold increase in the OY ratio ... adult survivorship soared very late in human evolution...
... Lee and I analyzed Middle Paleolithic humans from sites in western Asia dating to between about 110,000 and 40,000 years ago. Our sample included both Neandertals and modern humans, all associated with the same comparatively simple artifacts. ... We found that the Neandertals and modern humans from western Asia had statistically identical OY ratios...
Caspari claims that the great leap in longevity occurred within the past 45,000 years. She seems to think this was a cultural change, but I don't follow her logic. Most modern hunter gatherers age and die at the same rate as eurasians.
In modern human terms forty thousand years is a long time ago. But recent sequencing of 100 year old DNA suggests the indigenous Australians split from other humans before then ...
... Based on the rate of mutation in DNA, the geneticists estimate that the Aborigines split from the ancestors of all Eurasians some 70,000 years ago, and that the ancestors of Europeans and East Asians split from each other about 30,000 years ago....
... the split times calculated by the Danish team are compatible with the more reliable archaeological dates, which record the earliest known human presence in Australia at 44,000 years ago. The Aborigines’ ancestors could have arrived several thousand years before this date.
There are a lot of Google hits on the life expectancy of the indigenous Australian. It is usually estimated at 15-20 years less than euro-Australians. That is not, however, all that different from the life expectancy of modern Russians. The data neither supports nor refutes Caspari's hypothesis, but it suggests things are, as usual, complicated.
Anything about the biology of the Australian aboriginal is very sensitive. It's easy to see why.
 Via Wikipedia, I have just learned that the scientific practice for dating is now BP for "before present," where the present is arbitrarily assigned to 1950 ACE. I've converted to BCE here.
 There's obviously no consensus on where to draw these largely artificial boundaries.
 The truly great explorers died before modern humans were born.
Update 1/30/2012: From a NYT review of the state of mongrel man (emphases mine):
... little is known about the Denisovans — the only remains so far are the pinky bone and the tooth, and there are no artifacts like tools. Dr. Reich and others suggest that they were once scattered widely across Asia, from the cold northern cave to the tropical south. The evidence is that modern populations in Oceania, including aboriginal Australians, carry Denisovan genes.