Working on this recent MSE question, I was led to the following conjecture :
Suppose that $n$ is an integer with at least one prime divisor $\geq 7$. Then $\Phi_n$ has at least seven non-zero coefficients.
I have checked this conjecture up to $n\leq 10^5$. It is not hard to treat the case when $n$ is of the form $p^a$ with $p\geq 7$. In the general case $n$ will be of the form $n=p^a m$ with $m$ coprime to $p$, and $\Phi_n=\Phi_{p^{a}}\Phi_m$. What is unclear to me is how non-zero coefficients are somewhat "preserved" when we multiply by $\Phi_m$ where $m$ is coprime to $p$.
UPDATE (10/18/2014) : One can assume without loss of generality that $n$ is square-free. Indeed, let $n=\prod_{k=1}^r {p_k}^{a_k}$ be the prime factorization of $n$, with prime $p_k$ and $a_k\geq 1$. Let $m=\prod_{k=1}^r p_k$ be the square-free part of $n$. If $\zeta$ is a $n$-th root of unity, then it is a primitive $n$-th root of unity iff $\zeta^\frac{n}{m}$ is a primitive $m$-th root of unity. It follows that $\Phi_{n}(X)=\Phi_{m}(X^\frac{n}{m})$, so that $\Phi_n$ and $\Phi_m$ share the same number of non-zero coefficients.
Here is my proof for the conjecture. As you mentioned, we can assume that $n=pm$ so that $p$ does not divide $m$.
Suppose that the conjecture is false and $\Phi_n(x)$ has at most $p-1$ nonzero coefficients: $$ \Phi_n(x) = \sum_{\ell=1}^{p-1} a_{d_\ell} x^{d_\ell} $$ with some exponents $d_1,\ldots,d_{p-1}$ and integer coefficients $a_{d_1},\ldots,a_{d_{p-1}}$.
By the pigeonhole principle, there is some integer $u$ such that none of $d_1+u$, ..., $d_{p-1}+u$ is divisible by $p$. Take such a $u$. Let $\varepsilon=e^{2\pi i/n}$ and $\varrho=e^{2\pi i/p}=\varepsilon^m$, and consider the following expression: $$ S = \sum_{j=1}^p \varepsilon^{jum} \Phi_n(\varepsilon^{jm+1}). $$ Among the numbers $m+1,2m+1,\ldots,pm+1$ precisely one is divisible by $p$; the other ones are co-prime with $n=mp$. So, among $\varepsilon^{m+1},\ldots,\varepsilon^{pm+1}$ there are $p-1$ primitive $n$th roots of unity and one number that has lower order, namely $m$. Therefore, the numbers $\Phi_n(\varepsilon^{m+1}),\Phi_n(\varepsilon^{2m+1}),\ldots,\Phi_n(\varepsilon^{pm+1})$ are all zeros except for exactly one. Hence, $S\ne0$.
On the other hand, $$ S = \sum_{j=1}^{p} \varepsilon^{jum} \sum_{\ell} a_{d_\ell} \varepsilon^{(jm+1)d_\ell} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^{p} \varepsilon^{jm(d_\ell+u)} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^{p} \varrho^{j(d_\ell+u)}. $$
It is well-known that $\sum\limits_{j=1}^p \varrho^{jK}=0$ for all integers $K$ that are not divisible by $p$. Applying this to $K=d_1+u,\ldots,d_{p-1}+u$, we can see that $$ S = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \sum_{j=1}^p \varrho^{j(d_\ell+u)} = \sum_{\ell} a_{d_\ell} \varepsilon^{d_\ell} \cdot 0 = 0. $$
We have proved both $S\ne0$ and $S=0$, the conjecture must be true.
In fact we proved that the exponents that occur in $\Phi_n$ form a complete residue system modulo $p$.