MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Let $G$ be the isometry group of a polyhedron (tetrahedron, ..., icosahedron), its order being $2n$. The natural representation of $G$ over the space $H_\ell$ of harmonic polynomials of degree $\ell$ may or may not be irreducible. It is certainly not if $2\ell+1\ge\sqrt{2n}$. Thus let us take $(n/2)^{1/2}\le l\le n.$ Because the representation is reducible, there exists a strict invariant subpace, thus a non-zero $P\in H_\ell$ such that the set of $P\circ R$ with $R\in G$ does not span $H_\ell$. Because $|G|>2\ell+1$, this is a counter-example.
Update. Suppose that the representation of $G$ over $H_\ell$ admits an irreducible component of multiplicity $\ge2$ (I suspect that there are exemples; does somebody knows one?). Then there does not exist a spherical harmonics $P$ such that the $P\circ R$ span $H_\ell$ when $R$ covers $G$. This is because we may decompose $H_\ell=F\oplus^\bot K$ with $K$ irreducible component and $P\in F$.
Let $G$ be the isometry group of a polyhedron (tetrahedron, ..., icosahedron), its order being $2n$. The natural representation of $G$ over the space $H_\ell$ of harmonic polynomials of degree $\ell$ may or may not be irreducible. It is certainly not if $2\ell+1\ge\sqrt{2n}$. Thus let us take $$\left(\frac{n}{2}\right)^{1/2}<\ell2\ell+1, (n/2)^{1/2}\le l\le n. Because the representation is reducible, there exists a strict invariant subpace, thus a non-zero P\in H_\ell such that the set of P\circ R with R\in G does not span H_\ell. Because |G|>2\ell+1, this is a counter-example. 1 Let G be the isometry group of a polyhedron (tetrahedron, ..., icosahedron), its order being 2n. The natural representation of G over the space H_\ell of harmonic polynomials of degree \ell may or may not be irreducible. It is certainly not if 2\ell+1\ge\sqrt{2n}. Thus let us take$$\left(\frac{n}{2}\right)^{1/2}<\ell2\ell+1\$, this is a counter-example.