What I think is somewhat particular about the challenge of teaching programming is that there quickly develops two distinct levels or types of thinking it's "difficult". I don't see "programming" as difficult in the same way that I don't see "writing papers" as difficult: it's a piece of cake to get words on the screen that make sense. Of course, writing a paper can be quite hard depending on the ideas you are trying to express. Similarly, I think everyone believes programming to be difficult depending on the underlying problem you are trying to solve (for example, no one thinks its easy to solve NP-Complete problems in NP time or to write fast games on slow devices).

However, what trips teachers up is that with some students the problem is that they can't even get past the first hump: getting meaningful things on the screen in the first place. It would be as frustrating as having a student in a college level writing course that always puts the words in his sentences in random order, and expects the reader to "know" what order to read them. Such a teacher would on the one hand be teaching tone and proper structure to one set of students, and basic rules of semantics to another. I recall many students in my CS classes just rearranging the syntax in their programs hoping the compiler would finally accept it. Clearly these students are having much different problems than the ones who simply get a little confused when they have a hard bug in their programs or find the idea of pointers unintuitive.