What you are probably forgetting is that both distance and time intervals between events seen by relatively moving inertial observers are affected by the Lorentz transformation.
It is true that if observer $B$ moves at speed $v$ relative to $A$, and calculates the "rate" given by distance travelled, as measured in frame $A$ divided by the time elapsed for that travel as measured in frame $B$, you will get a quantity with the dimensions of velocity that approaches infinity as $v\to c$. However, this quantity is not a useful velocity because it mixes quantities measured in two different inertial frames.
Let $B$ travel a speed $v$ relative to $A$ such that $B$ runs through an $A$-measured distance $v$ in unit time. There might be two pins, stationary with respect to $A$, a distance $v$ apart, and $A$ can verify that it takes unit time for $B$ to run the distance between them using clocks at the pins that have been properly synchronized.
Now look it is from $B$'s frame. The pins are moving by and the time taken to run between them is $1/\gamma(v)=\sqrt{1-\frac{v^2}{c^2}}$, which you already understand. However, from $B$'s perspective, the distance between the pins , also shrunken by the same factor is $v/\sqrt{1-\frac{v^2}{c^2}}$, so that the two effects cancel out and $B$ concludes that $A$ is moving relative to $B$ at velocity $-v$.
This result is known as relativistic reciprocity. It can be derived from basic symmetry assumptions, or it is often in first relativity courses taken as a postulate whence to derive the Lorentz transformation.
Another velocity-related quantity that may help your intuition and which genuinely does approach infinity as $v\to c$ is the rapidity. Rapidity works like the following.
You begin in frame $A$ and boost so that you now move at unit velocity relative to $A$ to reach frame $B_1$. You can choose any velocity at all as your unit.
Now you do the same again, i.e. make the same unit relative velocity boost from frame $B_1$ in the same direction as before.
Keep doing the same thing, so that at step number $n$, you boost from frame $B_{n-1}$ to frame $B_n$m in the same direction as all the other boosts.
Otherwise put, frame $B_n$ results from $n$ successive applications of unity velocity co-linear boosts.
Then the rapidity of this relative motion is proportional to the number of boosts. That is, we can define the rapidity of the motion of $B_n$ relative to $A$ as $k\,n$, where $k$ is some scaling constant that we are free to define. Let's just set $k=1$ for now (although the convention usually sets it to $1/c$).
It should also be clear that one can have a fraction of a unit velocity boost. A rapidity of $1/2$ results from the application to frame $A$ of a boost whose square (i.e. two successive applications thereof) boosts from $A$ to $B_1$.
Now, it is no more difficult in theory (see practical problems below) to make the $n^{th}$ boost than it is to make the first one. By Galileo's principle, this must be true: your physical situation, ability to accelerate and so forth cannot change whatever your relative velocity to any other observer (including those comoving with your motion at any former time). So it is clear that we can have a relative motion of any finite rapidity.
The universal signalling speed limit $c$ works as follow. The time dilation in each frame $B_n$ relative to frame $A=B_0$ increases with $n$, so that, from $A$'s standpoint, each successive jump adds less speed so that $B_n$'s speed, relative to the initial frame $A$, asymptotes to $c$. This is the mechanism that prevents greater than $c$ relative motion between observers: from the boosted observer's point of view, there's no barrier ever to your accelerating indefinitely.
No finite sequence of finite boosts can induce a relative speed of $c$, and $c$ corresponds to infinite rapidity.
Practical Problems with Large Rapidities
I spoke of practical problems. You're almost certainly going to vaporize yourself eventually if you try to move with speeds of an appreciable fraction of $c$ relative to the intergalactic matter and gas in any region. See Randal Munroe's "Relativistic Baseball" Whatif.
