Epimenides brings a paradox to the bible

Those who claim the infallibility of the bible might not have noticed something hidden in the book of Titus.  It is a version of a paradox attributed to a Cretian called Epimenides.  It is said that he made one immortal statement:

"All Cretians are liars."

As the Wikipedia article says, a paradox of self-reference arises when one considers whether it is possible for Epimenides, as a Cretian to have spoken the truth. 

In the book of Titus it appears in this form:

One of themselves, even a prophet of their own, said, The Cretians are always liars, evil beasts, slow bellies.

This witness is true. Wherefore rebuke them sharply, that they may be sound in the faith;
Titus 1: 12-13 (Authorised Version)


So are people from Crete always liars or is this one telling the truth?  When verse 13 says that this witness (evidence) is true, which part is true?  They can't both be true can they.

It seems that the Epimenides Paradox was regarded as a bit of a joke in the first century, and it is surprising to find a joke in the bible, even if when one is quite well hidden from modern eyes.