Recall that Maxwell's equations (in the absence of losses) require only that $n^2 = \epsilon\mu$. So when you take the square root, you are mathematically allowed to take either the positive or the negative square root.
Of course, then the question becomes, why would you want to take the negative square root? Clearly, this is only an issue if $\epsilon\mu > 0$; if $\epsilon\mu < 0$ (ie, if one is negative and one is positive), then the index of refraction becomes imaginary. That has its own set of complications, which is outside the scope of your question. The original paper by Veselago that Mew cites in a comment discusses the consequences of $\epsilon < 0, \mu < 0$, and explains why using $n < 0$ makes sense in that case.
Recall one of the steps in the derivation of the wave equation (Veselago gives these as as equation 5):
$$\mathbf{k}\times\mathbf{E} = \frac{\omega}{c}\mu \mathbf{H} \\
\mathbf{k}\times\mathbf{H} = -\frac{\omega}{c}\epsilon \mathbf{E}$$
These two equations define the handedness of the $\{ \mathbf{E}, \mathbf{H}, \mathbf{k}\}$ system: if $\epsilon, \mu > 0$, then these three vectors form a right-handed set. If $\epsilon, \mu < 0$, then these three vectors form a left-handed set. Why does that matter? Because the Poynting vector $\mathbf{S}$, which gives the energy flux, points in the direction of $\mathbf{E}\times\mathbf{H}$, so the triplet $\{\mathbf{E}, \mathbf{H}, \mathbf{S}\}$ always forms a right-handed set. As we saw from above, if $\epsilon, \mu > 0$, then the wavevector $\mathbf{k}$ points in the same direction as $\mathbf{S}$. But if $\epsilon, \mu < 0$, then $\mathbf{k}$ points in the direction opposite to $\mathbf{S}$. The direction of the wave vector gives you the direction of the phase velocity, and the direction of the Poynting vector gives you the direction of the group velocity. The fact that those two point in opposite directions requires the index of refraction to be negative.
So that's why $\epsilon < 0, \mu < 0$ gives you a negative refractive index. What are the consequences? There are three major consequences Veselago gives (though he gives them in a different order):
- refraction is reversed when passing between substances of $n<$ and $n>0$. The light refracts away from the normal when passing from a medium of lower $|n|$ to a medium of higher $|n|$, rather than refracting towards the normal.
- the Doppler effect is reversed. Instead of frequency increasing when the source moves towards the observer (and decreasing when the source moves away), frequency decreases when the source moves towards the observer.
- Cerenkov radiation points in a different direction. Instead of propagating at an acute angle $\theta $ relative to the direction of $\mathbf{k}$, it propagates at an obtuse angle $\theta$ relative to $\mathbf{k}$.