Why is $\log_{-2}{4}$ complex?

With the logarithm being the inverse of the exponential function, it follows that $ \log_{-2}{4}$ should equal $2$, since $(-2)^2=4$. The change of base law, however, implies that $\log_{-2}{4}=\frac{\log{4}}{\log{-2}}$, which is a complex number. Why does this occur when there is a real solution?

The exponential function is not invertible on the complexes. Correspondingly, the complex logarithm is not a function, it is a multi-valued function. For example, $\log(e)$ is not $1$ -- instead it is the set of all values $1 + 2 \pi \mathbf{i} n$ over all integers $n$.

How are you defining $\log_a(b)$? If you are defining it by $\log(b) / \log(a)$, then it too is a multi-valued function. The values of $\log(4)/\log(-2)$ ranges over all values $(\ln 4 + 2 \pi \mathbf{i} m)/(\ln 2 + \pi \mathbf{i} + 2 \pi \mathbf{i} n)$, where $m$ and $n$ are integers.

Do note that the set of values of this multi-valued function does include $2$; e.g. when $m =1$ and $n=0$.

How do you define $\log_{-2}x$ in general? Under what circumstances is it appropriate to apply that "law"?

When $a>0$, $a\neq 1$, and $x>0$, then $\log_a x$ is defined to be the real number $y$ such that $a^y=x$. The fact that there is a unique such $y$ needs to be shown to justify that this definition makes sense (and it does). Note that this also depends on defining what $a^y$ means when $a$ is a positive number and $y$ is a real number.

With this definition of the logarithm, if you have another number $b>0$, $b\neq 1$, then you can show that $\log_b x=\dfrac{\log_a x}{\log_a b}$. This is an appropriate application of the change of base "law," and most likely how you have seen it introduced.

Once you get into allowing negative bases and possibly complex exponents, things become murkier. For example, how could we claim that $0$ is the natural logarithm of $1$ when it is well known that $e^{2\pi i}=1$? Should we define $\log_a x$ to be some complex number $y$ such that $a^y=x$, and then stipulate that we'll take $y$ to be real when possible? How do we even define $(-2)^y$ in general when $y$ is not an integer? We have to get into using branches of the complex logarithm, so the answers will not be unique, and they won't match up with the usual "laws" that work out in the positive base case.

Closely related to this are the fallacies that arise from assuming that the "law" $(a^b)^c=a^{bc}$ is valid outside of the context where $a$ is positive, seen in another question.