Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false?
In number theory such problems do exist, eg. as Aaron Meyerowitz points out the one about the coefficients of the cyclotomic polynomials. From TCS I only know examples like the Evasiveness Conjecture that are still unsettled.
Note: This is more like an extended comment than an answer.
Here is a problem from combinatorics whose status is similiar in flavor to that of Evasiveness Conjecture:
Background. A Latin square of order $n$ is an $n × n$ matrix in which each element from {1, . . . , n} occurs exactly once in each row and column. Two Latin squares of order $n$ are said to be orthogonal if you get $n^2$ distinct ordered pairs when you superimpose them. A set of Latin squares are said to be mutually orthogonal if every pair of them are orthogonal. Let $N(n)$ denote the maximum number of mutually orthogonal Latin squares of order $n$.
It is known that $N(n)\leq n-1$ for all $n$. If $n$ is a prime power then we know that $N(n)=n-1$, but for general values of $n$ the status of lower bounds is wide open.
In a related not-quite answer to @jagadish's, after being defined, Costas arrays were quickly found for very small numbers, and were later found for sizes $p-1$, where $p$ is prime. However, it is open whether they exist for all $n$ and computer searches are making people believe that they do not exist for $n=32$.
