This example is more closely related to <a href="https://mathoverflow.net/questions/5449/combinatorial-results-without-known-combinatorial-proofs">a question of mine</a>, but I'll give it here anyway.

A graded poset $P$ is *Sperner* if no antichain is larger than the largest level $P_i$ of $P$.  This property is named after Sperner, who proved that the Boolean posets $B_n$ of subsets of $\{ 1, 2, ... n \}$ are Sperner.  the Boolean posets $B_n$ are also *rank-symmetric* because they satisfy $(B_n)_i = (B_n)_{n-i}$, i.e. ${n \choose i} = {n \choose n-i}$ and *unimodal* because the sequence $(B_n)_i$ is at first increasing and then decreasing.  

Let $G$ be a group acting on $\{ 1, 2, ... n \}$.  Then $G$ acts on $B_n$ in the obvious way by order- and grade-preserving automorphisms.  Define the quotient poset $B_n/G$ in the obvious way, which inherits the grading on $B_n$.  It's not hard to see that $B_n/G$ is also rank-symmetric.

**Theorem:**  $B_n/G$ is unimodal and Sperner.

The only known proofs of this theorem are algebraic (the one I know uses linear algebra), and even for special cases a purely combinatorial proof is not known.  For example, in the case that $n = ab$ is a product of two positive integers and $G = S_b \wr S_a$ we recover the poset $L(a, b)$ of Young diagrams that fit into an $a \times b$ box; then the above theorem implies that the coefficients of the q-binomial coefficient ${a + b \choose b}_q$ are unimodal.  This was first proven by Sylvester in 1878, and a combinatorial proof was not found until 1989.  A combinatorial proof of the Sperner property is still not known.  This example is all the more remarkable because the statement that $L(m, n)$ is Sperner requires almost no mathematics to understand.

**Edit:**  I should probably provide a reference.  This material is from some <a href="http://math.mit.edu/~musiker/rstan5-6.pdf">notes on algebraic combinatorics</a> by Stanley.