Why don't quaternions contradict the Fundamental Theorem of Algebra?
There is actually a more basic result at work here.
Proposition: Let $R$ be an integral domain and $R[x]$ be the ring of polynomials with coefficients in $R$. If $f \in R[x]$ has degree $n$, then $f$ has at most $n$ roots in $R$.
You have seen that this result is not true for polynomials with coefficients in the quaternions. But the quaternions are not an integral domain because multiplication is not commutative.
The result above says that a degree $n$ polynomial has at most $n$ roots; the fundamental theorem of algebra states that a degree $n$ polynomial has exactly $n$ roots for polynomials with complex coefficients.
EDIT: See the wonderful answer here for the exact spot where the usual proof of the above proposition breaks down in the case of the quaternions. It basically boils down to the fact that in the polynomial ring, the indeterminate $x$ commutes with all scalars, i.e., $ax = xa$ for all $a \in R$. But if $R$ is noncommutative then substituting $b \in R$ for $x$ may cause problems, as it is not always true that $ab = ba$.
dxiv answered the question perfectly in the comment; but let me elaborate.
The fundamental theorem of algebra states that every polynomial of the form
$$p(z) = a_{n}z^{n} + a_{n-1}z^{n-1} + \dots + a_{1}z + a_{0}$$ where each $a_{n}$ is a complex number.
can be factored as
$$p(z) = a_{n}(z - z_{1})\cdot(z - z_{2})\cdots(z - z_{n-1})\cdot(z - z_{n})$$
for some choice of complex numbers $z_{1},\cdots,z_{n}$.
Now, this is equivalent to saying there precisely $n$ solutions which lie in the complex numbers to the equation $p(z) = 0$, so long as we agree to count solutions in terms of their multiplicity.
Your example shows there are other solutions which lie within the Quaternion field. Since not all of your solutions are complex numbers, there is no contradiction.
Hope that helps.
Let me put my comments in an answer. As SpamIAm said, the FTA has a generalization in any integral domain :
If $R$ is an integral domain, then any polynomial $P \in R[x]$ of degree $n$ has at most $n$ roots (counted with multiplicity)
The proof is that : $\quad $(a field is commutative, otherwise we say a non-commutative field)
Any integral domain can be embedded in its field of fraction $K$
Any field $K$ can be embedded in its algebraic closure $\overline{K}$
In an algebraically closed field $\overline{K}$, the FTA is
Any polynomial $P \in \overline{K}[x]$ of degree $n$ has exactly $n$ roots (counted with multiplicity)
proof :
since $\overline{K}$ is algebraically closed $P \in \overline{K}[x]$ has at least one root $a \in \overline{K}$
if $F$ is a field, then $P \in F[x]$ and $ P(a) = 0$ for some $ a \in F \implies P(x) = (x-a)Q(x)$ for some $Q\in F[x]$ (see polynomial long division)
Repeating the factorization on $Q(x)$ you have $P(x) = C \prod_{j=1}^n (x-a_j)$
If $R$ is an integral domain and $P(x) = C \prod_{j=1}^n (x-a_j)$ with $a_j \in R$ and $C \ne 0$ then $P(b) = 0 \implies b = a_j$ for some $j$
This way you can see what steps fail for $\mathbb{H}$ a non-commutative field.