We study one-dimensional cellular automata whose rules are chosen at random from among $r$-neighbor rules with a large number $n$ of states. Our main focus is the asymptotic behavior, as $n \to \infty$, of the longest temporal period $X_{σ,n}$ of a periodic solution with a given spatial period $σ$. We prove, when $σ\le r$, that this random variable is of order $n^{σ/2}$, in that $X_{σ,n}/n^{σ/2}$ converges to a nontrivial distribution. For the case $σ> r$, we present empirical evidence in support of the conjecture that the same result holds.