Reading the Plato on it, vaguely sounds like someone describing continental drift, but in a way that would be easier for people of the time to understand.
I'm just imagining this im sure, they couldn't have known about it.
There's islands out there (canaries, azores). My guess is a big tsunami event happened, washed out some town, survivors show up in ports around the med saying the place has sunk because that's a pretty good descriptor of a tsunami for ancient people, and the legend goes from there.
The melting of the icecap raised the oceans worldwide by 400 feet. Sometimes very quickly (as meltwater lakes broke through barriers). (OTOH, tsunamis go away.)