If a "liar" is someone who lies occasionally, then there is no problem at all: the poet, while lying occasionally, this time spoke the truth.
If a "liar" is someone who lies always, then the poet's statement cannot be true: if it were, then he himself would be a liar who just spoke the truth, but liars don't do that. However, no contradiction arises if the poet's statement is taken to be false: the negation of "All Cretans are liars" is "Some Cretans aren't liars" (see [DeMorgan's laws]?), in other words: some Cretans sometimes speak the truth. This does not contradict the fact that our Cretan poet just lied.
Therefore, the statement "All Cretans are liars", if uttered by a Cretan, is false, but not paradoxical.
Even the statement "I am a liar" is not paradoxical; depending on the definition of "liar", it may be true or false.