If Zeno seemed to prove our perceptions cannot be trusted, how, then, can/does an Empiricist justify faith in their perceptions? I'm looking for various solutions (or justifications in the face of the paradoxes to maintain Empiricism) of these issues.
Not everyone agrees that the paradoxes have been solved, but they aren't strictly empirical problems either.
There's a sizable school of thought, myself mostly included, holding that calculus basically solves the problems. Most of Zeno's paradoxes are founded in the claim that one cannot completely infinitely many steps in any finite time - but calculus, and convergence of limits, especially as refined by Weierstrass, tells us that an infinite totality of steps may be traversed in finite time given their convergence in the limit. Thus the puzzle becomes a prompt for calculus to come in, and that's that.
From a different direction, note that the paradoxes depend on an infinitely fine-grained world. While quantum mechanics still has a way to go on figuring this out (and may be in practice impeded from ever doing so), it's arguable that the universe operates with a particular resolution. If this is the case (and as far as we know, it might be) then the intial premise of Zeno's paradoxes - that you can cut the universe up as many times as you want in any dimension - falls apart. In the same vein, it's worth noting that Aristotle claimed the ancient Atomists were inspired by Zeno's paradoxes to posit the existence of such limited resolution (On Generation and Corruption 316b34).
Last, I'd like to suggest a borderline metaphilosophical perspective: that Zeno's paradoxes are "merely academic". Obviously, whatever Zeno might say, if I jump off a cliff I will in practice hit the ground hard. An empiricist could take this reasoning and say, "look, your little paradoxes are fun to ponder, but watch this: I'm walking. I'm traversing infinitely many points in finite time. Whatever the paradoxes may say, time and time again my perceptions are proving reliable (within reasonable bounds). We can hardly permit our scientific enterprise to be held back by a thought experiment totally divorced from reality!"
This last thought reminds me of an apocryphal tale I vaguely recall: a fellow ancient, first confronted with Zeno's paradoxes, offers an incredulous stare. They take a step forward, look about significantly, and declare, "disproved!"
Aristotle can be considered as one of the earliest Empiricists, or perhaps better, that empricism was one side of his many-sided philosophical persona.
Aristotle already points out that the method of exhaustion is an adequate solution; but he considers that this isn't a sufficient resolution when all aspects of the situation are properly considered; he suggests that a solution lies in a proper consideration of what determination & indetermination means; and this seems to have a family resemblence to Whiteheads 'occasions of determination' particularly in the analysis of motion.