It is still not known whether the problem of determining whether a linear integer recurrence (of which the Fibonacci recurrence $F_n = F_{n-1}+F_{n-2}$, $F_1=F_0=1$ is the most well known) contains a zero is decidable or not. Even the case of recurrences of depth 6 is currently open. (I discussed this problem at http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/ .) We do have the famous Skolem-Mahler-Lech theorem that gives a simple criterion as to when the number of zeroes is finite, but nobody knows how to get from that to deciding when there is a zero at all. (This is perhaps the simplest example of a large family of results in number theory in which one has an ineffective finiteness theorem for the number of solutions to a certain number-theoretic problem (in this case, an exponential Diophantine problem), but no way to determine if a solution exists at all. Other famous examples include Faltings' theorem and Siegel's theorem.)
EDIT: See also this survey of Halava-Harju-Hirvensalo-Karhumäki from 2005 on this problem: http://tucs.fi/publications/view/?id=tHaHaHiKa05a
