Of course, when Epimenides of Crete says "all Cretans are liars", there is no paradox. Epimenides is lying; this means that not all Cretans are liars, i.e. that there exists at least one Cretan who tells the truth. This is entirely plausible. Indeed, suppose Crete were populated by just Epimenides and his brother Epidermis. It could be that Epimenides is a liar, while his brother tells the truth.

So the historically accurate version doesn't work. But having Epimenides say "I am a liar" does.