Evidence from radioisotope dating of mineral crusts in cases on the Mediterranean coast in Spain indicates that sea level fluctuated in an unexpected way in that time period (citing Dorale, J.A., et al. 2010. Sea-level highstand 81,000 years ago in Mallorca. Science 327(Feb. 12): 860).
Before the most recent ice age, sea level was about eight and a half feet higher than it is now. About 85,000 years ago, ice caps had trapped water lowering the sea level to about 67 feet below current levels (about 75 feet below their peak).
Then, for reasons that have no real explanation right now, sometime 80,000 to 82,000 years ago, sea levels rose about 72 feet to levels about 5 feet higher than they are now.
By 79,000 years ago, this anomaly had largely ended, and sea levels were 50 feet lower than they are now (a 55 foot drop).
The evidence doesn't tell us how fast this surge came and went, but evidence from the floods the filled the Mediterranean, four or five million years ago, and evidence from the flood that inundated the English Channel, suggest that these kinds of evidence happen more quickly than the accuracy of our dating techniques allow us to establish.
The search for major floods that really happened in the pre-historic human era, is driven in part by the deluge myth. A large number of Eurasian, Australian and American cultures that were isolated for millenia share a myth of a great flood that covered the world, killing all but a handful of survivors and then receding. The myth of Noah and the flood is most familiar version of the story to Westerners, but there are dozens (perhaps hundreds or thousands) of other versions of the story.
The geological evidence makes clear that there was never a flood that covered all of our mountaintops. It didn't happen. There isn't enough water in the world to do that and never has been.
So, where did this common myth come from?
There have been major sea level changes and floods in human history. Indeed, after volcanic activity, floods are among the most deadly disasters in human history. But, not all sea level changes and floods in geologic history are a good fit for these myths. Floods before humans evolved wouldn't have made their way into myth (in the same vein, the dinosaur extinction event 65 million years ago didn't make it into human myths).
But, a flood that is so universal in myths across the world would either have to have had a broad global scope and reached even people living thousands of feet above sea level, like the Inca, or have been a composite of multiple floods that were individually devastating and common, or have occurred before their ancestors diverged from each other.
If the ancestors of almost everyone who shares the deluge myth lived in some flood prone area, like a coast or a river's flood plain, it would have seemed like the whole world was affected.
The myth appears in the earliest written myths, found in Sumeria, and were shrouded in the legendary past at the time those myths were recorded, around 5000 years ago. So, if the myths all record a single event, they have to have happened before then.
Not all the myths are independent. For example, the story of Noah is very likely to have its roots in the Sumerian version of the story. But, many of the cultures that share the myth diverged in pre-Neolithic times (i.e. around the time of the end of the last ice age). (Note that since Nilo-Saharan people may have also lived on the North African coast in that time period, and migrated South from there as the Sahara dried up, so it wouldn't be inconsistent for people of those cultures to share the myth even though they don't live there now, although I'm not aware that these people do have a deluge myth.)
The flood that the mineral deposits point to about 80,000-82,000 years ago is the only known flood of epic scale that happened between 100,000 and 60,000 years ago in a place inhabited by modern humans, the time period and place where all the cultures that share the myth had a common ancestor. So, it is plausible that this single, geographically confined event that could have spawned all of the deluge myths.
This is hardly definitive proof. The physical evidence that such a flood even happened about 82,000 years ago deserves skepticism as it is thin for such a remarkable claim, when there isn't any obvious mechanism to make it happen. But, the physical evidence of its apparent timing and scale make it a plausible candidate for a source of such a pervasive myth. Clearly, this deserves more study, both for its climatological importance, and its anthropological importance.
UPDATED: Copy edits made February 16, 2010 in response to comments and for a general cleanup. A summary of African flood myths can be found here. An effort to group these African stories by languages produces the following:
Cameroon, Masai, Komililo Nandi, Kwaya (Lake Victoria), Pygmy
Southwest Tanzania, Ababua, Kikuyu (Kenya), Bakongo (west Zaire), Bachokwe (southern Zaire), Lower Congo, Basonge, Bena-Lulua (Congo River, southeast Zaire)
Yoruba (southwest Nigeria), Efik-Ibibio (Nigeria), Ekoi (Nigeria)
Mandingo (Ivory Coast)
A Mediterranean flood, thus, would require some story transfer to neighboring cultures from Nilo-Saharan people, and/or for people to have lost their language to Niger-Congo based farming peoples while retaining their stories. But, the lack of close match stories in Southern Africa is somewhat supportive of a common Mediterranean origin for the myth. Some of the Africa flood stories that are known are only dim matches to the deluge myth and could be independent, while others like the Masai version, are quite similar to Eurasian versions.
A flood around 81,000 years ago in the Mediterranean that caused mass death, could also cause a population bottleneck in that time period. See also here.
The deepening of the ice age caused by the Toba Volcano eruption (of about 75,000 to 70,000 years ago) is another theory. See also here. (Note, links illustrative of basic ideas of the theory only and not intended authority for their correctness.)
While it requires an early estimate for the Toba eurruption and an early date for the sea level rise following a high point 80,000 years ago, one theory that would make sense to explain the sea level change discussed would be rising sea levels caused by the end of an ice age that otherwise would have run from about 100,000 years ago to 80,000 years ago, which was reversed by sudden global cooling in the wake of the Toba Volcano eruption, that in turn lowered sea levels again.