That is Zeno's paradox of motion, which dates back to the 5th Century BCE.
The modern answer is based on calculus, namely that an infinite geometric series can in fact converge. As Wolfram Alpha phrases it, "the infinite number of "half-steps" needed is balanced by the increasingly short amount of time needed to traverse the distances."
There are plenty of other paradoxes, such as the Russell's Paradox:
"R is the set of all sets that do not contain themselves. Is R contained in R?"
(This type of set construction is typically ruled out by ZFC.)
Or, Quine's paradox, which avoids the self-reference underlying many paradoxes:
"yields falsehood when preceded by its quotation" yields falsehood when preceded by its quotation.
Anyway.... Some terminological clarifications are probably required. "Logic" is actually a specific field which is used to determine the validity of inferences. Modern logicians don't see their tools as "measuring everything," and have known for quite some time that there are boundaries to logic. The most critical of these was articulated by Kurt Godel, who proved that any axiomatic logical system capable of constructing arithmetic will either be inconsistent or incomplete, but cannot be both. (I.e. if your logical system is truly complete, then it will allow inconsistencies, and that renders your logical system useless; and if you exclude those inconsistencies, then it can't be complete.)
The person you were talking to may have meant terms like "reason" or "rationality," which is not the same thing. It's a common example of using a technical term according to a non-technical meaning.