How do I interpret uncertainty in velocity greater than the speed of light?

The right formula is $$\Delta X \Delta P \geq h/4\pi$$ where $P$ is the momentum which is approximatively $mv$ only for small velocities $v$ when compared with $c$. Otherwise you have to use the relativistic expression $$P = mv/ \sqrt{1-v^2/c^2}.$$ If $\Delta X$ is small, then $\Delta P$ is large but, according to the formula above, the speed remains of the order of $c$ at most. That is because, in the formula above, $P\to +\infty$ corresponds to $v\to c$.

With some details, solving the above identity for $v$, we have $$v = \frac{P}{m \sqrt{1+ P^2/m^2c^2}}\:,$$ so that $$v\pm \Delta v = \frac{P\pm \Delta P}{m \sqrt{1+ (P\pm \Delta P)^2/m^2c^2}}.$$ We have obtained the exact expression of $\Delta v$: $$\pm \Delta v = \frac{P\pm \Delta P}{m \sqrt{1+ (P\pm \Delta P)^2/m^2c^2}} - \frac{P}{m \sqrt{1+ P^2/m^2c^2}},$$ where $$\Delta P = \frac{\hbar}{2\Delta X}\:.$$ This is a complicated expression but it is easy to see that the final speed cannot exceed $c$ in any cases. For a fixed value of $P$ and $\Delta X \to 0$, we have $$v\pm \Delta v = \lim_{\Delta P \to + \infty}\frac{P\pm \Delta P}{m \sqrt{1+ (P \pm \Delta P)^2/m^2c^2}}= \pm c\:.\tag{1}$$

Finally, it is not difficult to see that (using the graph of the hyperbolic tangent function) $$-1 \leq \frac{(P\pm \Delta P)/mc}{ \sqrt{1+ (P \pm \Delta P)^2/m^2c^2}}\leq 1\tag{2}\:.$$ We therefore conclude that $$-c \leq v\pm \Delta v \leq c,$$ where the boundary values are achieved only for $\Delta X \to 0$ according to (1). Relativity is safe...

What you've discovered is that "normal" Quantum Mechanics is incompatible with relativity. As Valter Moretti pointed out, using a relativistic expression for momentum solves this problem. There are, however, more problems that cannot be solved by simply using relativistic expression for energy and momentum. For example,

• The relativistic equation $E=mc^2$ implies that it is possible for energy to be converted into new particles. The time-energy uncertainty principle $\left(\Delta E\cdot\Delta t\geq\hbar/2\right)$ implies that it is possible for particles to be created out of thin air, even when, from a classical viewpoint, there is not enough energy present.
• Even when single-particle quantum mechanics is modified to use a relativistic Hamiltonian, as in the Klein-Gordon equation, there is always a non-zero probability that a particle can teleport across a space-like interval (faster than the speed of light).

These problems are resolved by the introduction of Quantum Field Theory. Basically, instead of quantizing individual particles, we quantize fields. The particles are excitations of the fields, and new particles can appear out of thin air. Quantum field theories are designed to preserve causality so that they work well with relativity. The mathematics is all very complicated, but that's the basic idea.

There are two problems with this setup. The first is here:

Assume an electron which is moving very slowly

If you know already that the electron is moving very slowly then you already have a small uncertainty in momentum. For example, if you know that the electron is moving at less than $1 \text{ m/s}$ then $\Delta v = 0.29 \text{ m/s}$ so we already have $\Delta p = 2.6 \ 10^{-31}\text{ kg m/s}$. By $\Delta x \ \Delta p \ge \hbar/2$ then $\Delta x \ge 0.0002\text{ m}$ so the distance uncertainty mentioned in the setup is not possible.

Of course, perhaps you meant something different by "moving very slowly", but if you work through the numbers then $\Delta x = 10^{-13}\text{ m}$ gives an uncertainty of velocity $\Delta v \ge 0.88 \ c$ which would be hard to justify as "very slowly" regardless.

EDIT: Per the comment below "very slowly" refers to a non-relativistic velocity. If we insist on $\gamma < 1.01$ then that corresponds to $v < 4.2 \ 10^7 \text{ m/s}$. This is $\Delta v < 1.2 \ 10^7 \text{ m/s}$ or a maximum of $\Delta p = 1.1 \ 10^{-23} \text{ kg m/s}$. So by Heisenberg's uncertainty principle the minimum uncertainty in position is $\Delta x > \hbar/(2\Delta p) = 4.8 \ 10^{-12}\text{ m}$

The second problem is

using the formula $$\Delta x. \Delta v\ge \frac{h}{4\pi m}$$

The correct expression is $\Delta p \Delta x\ge \hbar/2$. This is important because $p=mv$ is only a non-relativistic approximation. In relativity $p=mv/\sqrt{1-v^2/c^2}$ which is unbounded as $v$ approaches $c$. With this correct formula $\Delta x = 10^{-13}\text{ m}$ results in $\Delta p = 5.3 \ 10^{-22} \text{ kg m/s}$. As indicated above, for an electron this corresponds to a velocity uncertainty of $\Delta v = 0.88 \ c$ which is quite large, but does not exceed $c$.