Why don't quaternions contradict the Fundamental Theorem of Algebra? I don't pretend to know anything much about the Fundamental Theorem of Algebra (FTA), but I do know what it states: for any polynomial with degree $n$, there are exactly $n$ solutions (roots). 
Well, when it comes to quaternions, apparently $i^2=j^2=k^2=-1$, but $i\ne j\ne k\ne i$. So now, we have apparently found three solutions to the second-degree polynomial $x^2=-1$.
I'm not aware of the justification of the FTA, nor I am I aware of Hamilton's justification for quaternions. However, I know a contradiction when I see one. What am I missing here?

You already have plenty of answers, but I'd like to add some information in the hope that it might help other students, not only you. You wrote "I do know what [FTA] states: for any polynomial with degree $n$, there are exactly $n$ solutions (roots)." What you quoted here is not the FTA but rather the conclusion half of the FTA. You omitted the hypothesis half, which is that the coefficients of the polynomial and the roots that are being counted are complex numbers. As the other answers have explained, the hypothesis is not satisfied when you're dealing with quaternions, as these are not complex numbers, so there's no reason to expect the conclusion to be true.  The reason I'm rehashing this information is that your problem here is one that I've seen very often in teaching various levels of mathematics: a tendency to pay attention only to the conclusion of a theorem, ignoring the hypothesis.  Some students seem to feel that the hypothesis is there only because mathematicians like to make theorems look complicated.  As you found here, the hypothesis is there because we like to make theorems be correct; if you omit (or ignore) the hypothesis, you get false statements, like the statement that quadratic polynomials should have only two quaternion roots.  So the moral of this sermon is that, when learning a theorem, you need to learn the whole theorem, hypothesis and conclusion. Learning only the conclusion leads to errors.
