What I don't agree with is pointers and recursion making people's heads explode. Pointers are just another language construct and with enough practice anyone will get used to them. Recursion is a mathematical concept. Thus, for all its elegance and simplicity, people still find it difficult in the same way they find mathematics difficult.
The real weeder classes that I've seen are generally theory and discrete math classes. The truly challenging systems and programming related classes usually aren't offered until the latter years of a student's CS career (such as OS, Distributed Systems, etc).
Disclaimer: My experiences come only with my university - Carnegie Mellon, and chatting with friends from others