[Tainnor]

The way to see it is to realise that the eigenvalues are the roots of the characteristic polynomial (which is not hard to prove). But by the fundamental theorem of algebra, every complex polynomial has a root (it does actually have n roots, where nxn is the dimension of the matrix, but those roots can all be the same). This also shows why the theorem is, in general, false if you restrict yourself to real numbers.

(I also think that the counterexample exhibited "counts" in the way that it's intuitively very clear why it can't have a real eigenvector. The R^2 plane can be easily visualised, as opposed to C^2, and the matrix exhibited acts as a rotation of R^2, so of course there can't be an eigenvector. As you said, once you allow complex numbers, that's not true anymore, but at that point the visual intuition breaks down somewhat.)