Why do congruence conditions not suffice to determine which primes split in non-abelian extensions?

Here's an answer for the special case when the base field is $\mathbb{Q}$. It involves a large bit of class field theory over $\mathbb{Q}$, so I'll be terse.

We start with the lemma which Buzzard mentioned.

Lemma - Let $K$, $L$ be finite Galois extensions of $\mathbb{Q}$. Then $K$ is contained in $L$ if and only if $\operatorname{sp}(L)$ is contained in $\operatorname{sp}(K)$ (with at most finitely many exceptions).

The proof of the lemma follows from the Chebotarev Density Theorem.

We now show that if the rational primes splitting in $K$ can be described by congruences, then $K/k$ is abelian.

Proof. Assume that the rational primes splitting in $K$ can be described by congruences modulo an integer $a$. This allows us to assume that $\operatorname{Sp}(K)$ contains the ray group $P_a$. The next step is to show that the rational primes lying in $P_a$ are precisely the primes of $\operatorname{sp}(\Phi_a(x))$. By the above lemma, this means that $K$ is contained in a cyclotomic field, hence is abelian.

OK how's about this to finish (I don't think either argument posted so far deals with this case). Say $K/\mathbf{Q}$ is finite and (away from a finite set of exceptions) $p$ splits completely in $K$ iff $p$ mod $N$ is contained in a subset $S$ of $(\mathbf{Z}/N\mathbf{Z})^\times$. I think the other two answers just deal with the case when $1\in S$ (where they show $K$ is contained in $\mathbf{Q}(\zeta_N)$). But if $1\not\in S$ then only a finite number of primes split completely in the compositum of the Galois closure of $K$ and $\mathbf{Q}(\zeta_N)$ and that's a contradiction. So now I think between us we have completely answered the question.

Fix a number field $K$. For an integer $m$, let $S_1(m,K)$ be the congruence classes $a$ mod $m$ that contain infinitely many primes $p$ such that $p \mid \mathfrak p$ for some prime $\mathfrak p$ of $K$ satisfying $f(\mathfrak p|p) = 1$. (That was a mouthful: $p$ is lying below some prime of $K$ with residue field degree 1.) If $K/\mathbf Q$ is Galois, then such $p$ are the primes splitting completely in $K$, up to finitely many exceptions (among the ramified primes). That is, when $K/\mathbf Q$ is Galois, $S_1(m,K)$ is the set of congruence classes mod $m$ containing infinitely many primes which split completely in $K$. (The prime numbers that split completely in a number field are identical to the prime numbers that split completely in its Galois closure over $\mathbf Q$, so attempting to describe such "split sets" by congruence conditions could just as well assume the number field is Galois over $\mathbf Q$. I am working over base field $\mathbf Q$ throughout.)

As Kevin has suggested, it is not obvious at first that these sets $S_1(m,K)$ have much structure, particularly that they contain $1$ mod $m$. By the pigeonhole principle, any $S_1(m,K)$ is certainly a nonempty set, and it is a subset of the unit group $(\mathbf Z/m)^\times$ rather than just $\mathbf Z/m$, but this is kind of superficial.

A good reason (the right reason?) that $1$ mod $m$ is in $S_1(m,K)$ is that $S_1(m,K)$ is actually a subgroup of $(\mathbf Z/m)^\times$. In fact, under the usual identification of $\mathrm{Gal}(\mathbf Q(\zeta_m)/ \mathbf Q)$ with $(\mathbf Z/m)^\times$, $S_1(m,K)$ is the image of the restriction homomorphism $\mathrm{Gal}(K(\zeta_m)/K) \longrightarrow \mathrm{Gal}(\mathbf Q(\zeta_m)/\mathbf Q)$. For a proof, see Theorem 3 at

http://www.math.uconn.edu/~kconrad/blurbs/gradnumthy/dirichleteuclid.pdf

and Theorem 4 there is a generalization where $(\mathbf Z/m)^\times$ is replaced with any Galois group of number fields.