Paul apparently had a low opinion of the people of Crete. This is Titus 1:12-13:
The man Paul is talking about is Epimenides, and his statement is sometimes called the "Epimenides paradox". The supposed problem here is this: if the statement Epimenides made was true, then he wasn't lying... but he himself was a Cretan... so Cretans aren't always liars...
But this is an overly literal way of interpreting the phrase "always liars". There's nobody on Earth whose every statement is false. Indeed, such a person would be a very ineffective liar, since you could just assume that the opposite of what he said was the truth. Rather, someone who is "always a liar" lies only when he thinks it's in his interests to do so.
A more serious problem is the idea that a whole society can be as dishonest as Paul seems to think. But Paul also took a dim view of humankind generally, and so was not being much more harsh on Cretans than he would be on anyone else.
The Epimenides paradox isn't much discussed in philosophical circles, since it's so weak, though I should note that the standard solution is that the statement is actually false. But - for the reasons above - I think it's obvious that the statement could be broadly true in the manner that Epimenides and Paul intended it. A much sharper paradox is the "liar paradox", which is as follows:
If it's false, then what it asserts is actually the case. But then it's true. In which case, it must be false, since that's what it says. Anyway, you might occasionally see this genuine paradox mentioned in the same breath as the Epimenides case, but in reality only this latter version is an interesting problem.