There is no particular theoretical problem with complex roots of characteristic polynomials. But if we want to avoid explicit mention of powers of a non-real number, there is some extra work to do.
The (almost) simplest example is $a_{n+2}+a_n=0$, with say $a_0=1$ and $a_1=-1$.
The roots of the characteristic polynomial are $i$ and $-i$. So the general solution is $Ai^n+B(-i)^n$. To find $A$ and $B$, use the initial conditions.
From the value of $a_0$, we find that $A+B=1$. From the value of $a_1$, we find that $Ai-Bi=-1$, or equivalently $A-B=i$.
Solve. We obtain $A=(1+i)/2$ and $B=(1-i)/2$.
So the solution to our recurrence is given by $a_n=\frac{1+i}{2}i^n +\frac{1-i}{2}(-i)^n.$
This is correct, but not entirely satisfying! So let's simplify.
Note that $i^n=1$ if $n \equiv 0 \pmod{4}$, $i^n=i$ if $n \equiv 1 \pmod{4}$, $i^n=-1$ if $n \equiv 2\pmod 4$, and $i^n=-i$ if $n\equiv 3\pmod{4}$.
Compute. When $n\equiv 0\pmod 4$, we get $a_n=1$. When $n \equiv 1 \pmod {4}$, we get $a_n=-1$, and in the other two cases we get $a_n=-1$ and $a_n=1$ respectively.
There are of course more complicated situations. If our root is $a+bi$, it may be useful to express $(a+bi)^n$ in polar form. There is a number $\theta$ such that $a+bi=c(\cos\theta+i\sin\theta)$, where $c=\sqrt{a^2+b^2}$. Then $(a+bi)^n=c^n(\cos n\theta +i\sin n\theta)$. If the $a_n$ are real, we may wish to express $a_n$ using powers of a real number and sines and cosines.
The complex solutions of the characteristic equation will come in complex conjugate pairs. It turns out that we can use $\cos\theta=(e^{i\theta}+e^{-i\theta})/2$ and $\sin\theta=(e^{i\theta}-e^{-i\theta})/2i$ to get rid of all mention of $i$ in the expression for $a_n$, if we so wish.
Added: What does this have to do with analysis of algorithms? In general, probably not much. I would expect that most of the time, the roots of the characteristic equation will be real.
Even when not all the solutions are real, I would expect that the "norms" of the non-real roots will be smaller than the norm of at least one real root. (The norm of $a+bi$ is $\sqrt{a^2+b^2}$.)
What this means practically is that the contribution of the non-real roots to the size of $a_n$ is, for large $n$, negligible in comparison with the contribution of the largest real root.