  We study generalized Fibonacci sequences $F_{n+1}=PF_n-QF_{n-1}$ with initial
values $F_0=0$ and $F_1=1$. Let $P,Q$ be nonzero integers such that $P^2-4Q$ is
not a perfect square. We show that if $Q=\pm 1$ then the sequence
$\{F_n\}_{n=0}^\infty$ misses a congruence class modulo every prime large
enough. On the other hand, if $Q \neq \pm 1$, we prove that (under GRH) the
sequence $\{F_n\}_{n=0}^\infty$ hits every congruence class modulo infinitely
many primes.
