The Garamantes, referred to by Herodotus, are generally considered to have been the first Libyan empire. However, attempts to link them to the Atlantis story would appear to be undermined by the fact that they flourished around the middle of the first millennium BC, which is far too recent to fit any interpretation of Plato’s 9,000 ‘years’, be they solar, lunar or seasonal.
Frank Joseph identifies the Garamantes with the Sea Peoples whom he considers to have been Atlantean refugees. However, the Garamantes are generally accepted as having developed urban centres in what is now southern Libya(a)(b), which is not what you might expect from a maritime culture.
(a) http://www.archaeology.org/0403/abstracts/sands.html
(b) http://www.innovations-report.com/html/reports/earth_sciences/report-54055.html

