This paradox can be answered like this:
The cretan first says that all cretans are liars - he means to say that all cretans tell lies, it doesn't matter when or how may times, but they lie a lot (to make it simple, they are cunning enough to easily tell lies)
The second time he says that he speaks the truth - that means that cretans do tell lies, but can occasionally be truthful. in this case he is just confusing, but he speaks the truth as he says that cretans are liars (he speaks the truth about cretans BEING liars, aka, the first statement).
So he's not literal in his statements