What are conjectures that are true for primes but then turned out to be false for some composite number? Note: This is an update formulation since many people misunderstood the question before.
Of course it is easy to make a statement like "Every n is a prime or at most 1000", which is true for every prime $n$ and every small $n$ but fails for $n=1002$. What are "real" conjectures that were known to hold for primes and small values, then turned out to be false?
An excellent example about cyclotomic polynomials was given by Aaron in the comments. Here the conjecture was that the coefficients are $0, \pm 1$ for every $n$. This holds for primes and small $n$'s, but fails for $105$.
Also the existence of Carmichael numbers comes close, but here the problem itself involves primes, I would like something less "primey". I know conjuctures that are or were known only for primes. Recently solved is Colorful Tverberg, still unknown is Evasiveness or this little MO problem.
 A: Frankl and Wilson proved a certain theorem about set-systems with certain restrictions on their order and the order of their intersections modulo $p$ for $p$ prime, and wrote "it would be interesting to know whether it holds for composite $p$ as well" [1].
Frankl gave a counterexample for $p=6$, and Grolmusz [2] gave strong counterexamples for all $p$ with at least two prime factors.
[1] Frankl, P.; Wilson, R. M.
Intersection theorems with geometric consequences.
Combinatorica 1 (1981), no. 4, 357–368.
http://www.ams.org/mathscinet-getitem?mr=647986
[2] Grolmusz, Vince
Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs.
Combinatorica 20 (2000), no. 1, 71–85. http://www.ams.org/mathscinet-getitem?mr=1770535; 
A: An aliquot sequence is a recursive sequence in which each term is the sum of the proper divisors of the previous term. Catalan conjectured that no aliquot sequence is unbounded. The conjecture is trivially true for primes, since the aliquot sequence for $p$ is $p,1,0$ (terminating, since the sum of the proper divisors of zero is undefined). The conjecture is also true, by computation, for all $n\le275$. Strictly speaking, this doesn't qualify as an answer to the question, since there is no $n$ for which the conjecture has been proved to be false, but there are so many integers for which the aliquot sequence shows no sign of ever reaching a bound that it seems most plausible to conclude that the conjecture is false. 
Here is a website dedicated to the problem. 
A: An important question in matroid structure theory is given a matroid $M$, how many inequivalent representations does it have over a fixed finite field $\mathbb{F}$?  Two $\mathbb{F}$-matrices $A$ and $B$ are equivalent if they are related by a projective transformation, in which case they clearly represent the same matroid.  
In 1988, Kahn proved that $3$-connected $GF(4)$-representable matroids have a unique representation over $GF(4)$.  In the same paper, he conjectured that for every prime power $q$, there is an $n(q)$, such that every $3$-connected $GF(q)$-representable matroid has at most $n(q)$ inequivalent representations. Oxley, Vertigan and Whittle proved Kahn's conjecture for $GF(5)$, but also showed that it fails for all larger finite fields.  This naturally led to the question of what happens for $4$-connectivity, and the following weakening of Kahn's Conjecture. 
Conjecture 1. For every prime power $q$, there is an $n(q)$ such that every $4$-connected $GF(q)$-representable matroid has at most $n(q)$ inequivalent representations over $GF(q)$.
One would expect that Conjecture $1$ holds for all finite fields, or fails for sufficiently large finite fields. However, remarkably there is a dichotomy depending on whether $q$ is prime!  
Theorem 2. (Geelen and Whittle) For every prime $p$, there is an $n(p)$ such that every $4$-connected $GF(p)$-representable matroid has at most $n(p)$ inequivalent representations over $GF(p)$.
The proof of Theorem $2$ is not easy; the paper is $175$ pages.  
Theorem 3. (Geelen, Gerards and Whittle)
For every non-prime power $q \geq 9$, there is a $4$-connected $GF(q)$-representable matroid with arbitrarily many inequivalent representations over $GF(q)$. 
A: Once it was conjectured (for a short time) that $2^p-2$ cannot be divisible by $p^2$ when $p$ is prime. The two known counterexamples are $1093$ and $3511$. For more detail and context read here.
A: The internal multiplicative structure of the set {1,2,3,...,n} may be mapped into a group of order n, preserving this multiplication. This is clearly possible when n+1=p, p a prime, just reduce mod p and when 2n+1=p, just use the squares mod p. But fails for composite values, for example 195.  
Are there any other such maps for large values of n. One can always find a map when n<195. However they appear to get sparse for large values of n , except for those noted above.
A: I'll elevate my comment to an answer and give two more related ones. One seems less trivial for primes but has first exception at $30$, the other seems more obvious for primes but has first exception at $900$.
The cyclotomic polynomials $\Phi_d$ can be specified inductively by saying that, for all $n$, $\prod_{d|n}\Phi_d(x)=x^n-1.$ Equivalently, $\Phi_d(x)$ is the minimal polynomial of $e^{{2\pi i}/d}.$ It turns out that $\Phi_{15}=x^8-x^7+x^5-x^4+x^3-x+1.$ One might conjecture that the coefficients of $\Phi_m$ are always are always $0,1$ and $-1.$ This is true for primes, prime powers and even for numbers of the form $2^ip^jq^k$ (up to two distinct odd prime divisors) but it fails for $m=105$
The second example is of great interest to me, but takes a little explanation For a finite integer set $A$, we say that $A$ tiles the integers by translation if there is an integer set $C$ with $\{a+c \mid a \in A,c \in C \}=\mathbb{Z}$ and each $s \in \mathbb{Z}$ can be uniquely written in this form. Then we write $A \oplus C =\mathbb{Z}$.  This property is not affected by translation so we will always assume that $0 \in A$ and $0 \in C.$ 
Consider this property enjoyed by certain integers $m$: 

Whenever $A$ is an $m$ element set with $A \oplus C=\mathbb{Z}$  there is a prime divisor $p$ of $m$ such that $A \subset p\mathbb{Z}$ or $C \subset p\mathbb{Z}.$ 

It is true when $m$ is prime (but I don't consider it trivial) and also when $m$ is a prime power or a product $m=p^iq^j$ of two prime powers. It is not true for $m=30$ and other values with at least three distinct prime factors. The sets $A$ which provide counterexamples are rather spread out. If I recall correctly , a counterexample for $m=30$ will have $\max{A} \gt 720$ (if we set $\min{A}=0$. )
Here is a variant form: Write $A \oplus B=\mathbb{Z}_n$ when $A \oplus B$ is a complete set of residues $\mod n=|A||B|.$ Here we will assume $0=\min{A}=\min{B}$ and consider this property which is enjoyed by certain integers $n$. 

Whenever $A \oplus B=\mathbb{Z}_n$ , there is a prime divisor $p$ of $n$ such that $A \subset p\mathbb{Z}$ or $B \subset p\mathbb{Z}.$ 

It always holds when $n$ is a prime, or prime power or even a product of two prime powers $n=p^jq^k.$ It fails when both $|A|$ and $|B|$ can have three distinct prime divisors so the first time is for $n=2^23^25^2=900$ as well as for $n=2\cdot3\cdot5\cdot 7 \cdot 11 \cdot 13=30030.$ So, while this seems trivial as a property of $n=|A||B|$, it is actually a property of $\min(|A|,|B|)$ (although it would take longer to explain why) and  is not trivial when that minimum is a prime.
Now that I got to the property resisting digressions, let me explain why it is interesting (optional), mention the existence of an open problem and demystify the property a bit. For details see Tiling the integers with translates of one finite set which also proves the claims above and shows a link to cyclotomic polynomials.
It is interesting to characterize finite sets $A$ which tile the integers by translation: $A \oplus C=\mathbb{Z}.$ There are attractive sufficient conditions (T1 and T2 in the linked paper). These conditions are necessary when the size has at most two prime divisors, $|A|=p^{\alpha}q^{\beta}.$ The method of proof depends strongly on the property above. It is also not hard to show that if $A \subset p\mathbb{Z}$ (all elements of $A$ are multiples of $p$) Then there is $C$ with $A \oplus C=\mathbb{Z}$ if and only if there is a set $C'$ with $A' \oplus C'=\mathbb{Z}$  where  $A'=\lbrace\frac{a}{p} \mid a \in A \rbrace.$ ` This reduction to a smaller case (along with the rest and a bit more) is what allows the proof that the sufficient conditions are also necessary for a set of size $|A|=p^{\alpha}q^{\beta}$ to tile the integers by translation. It is possible that the conditions are necessary  for $A$ of any finite size, however the method of proof would have to be quite different. The first potential exception would be for $A$ with $30$ elements which tiles $\mathbb{Z}_{900}.$
Here is a way to restate the property above so that it does hold for all $m$ (but fails in general to allow the proof of necessity): If $A \oplus B=\mathbb{Z}_n$ then for one of the two sets , say $A$, none of the differences $a_i-a_j$ is coprime to $n$. Since $0 \in A$ this means that also every $a \in A$ shares a divisor with $n.$ So if $n=72$ then every member of $A$ and every difference is divisible by $2$ or $3$ or both. In fact they are all even or all multiples of 3 lest there be $a_x \in A$ not divisible by $2$ and $a_y \in A$ not divisible by $3$ as then $a_x-a_y$ would share no prime divisors with $72.$ So the reduction is possible and a theorem can be proved. When $A$ has 30 elements it can be the case that among them are $6,10,15$ and various of their multiples so the elements and differences all share a divisor with $30$ but no one divisor covers all cases and the proof is not available.
