Infinity is a very tricky subject, and trying to talk about it using only our
intuition is a pretty certain way to create seeming
paradox, because
infinity and human intuition don't match up very well.
Even if the universe is infinite, movement relative to a given point is still possible. For example, there are an infinite number of real numbers, but we still know the exact distance between any two of them.
I think the fundamental problem with this "paradox" is that it divides space infinitely, but not time. As we keep dividing the distance to travel, we must also divide the time that will be required to travel it. As the size of the distance to travel approaches 0, so to will the time required to travel it.