1. Learning to think algorithmically; 2. Abstraction.
What do I mean by these? By "thinking algorithmically," I really mean "taking a large problem and breaking it up into an ordered series of steps or sub-problems." This is surprisingly hard for a lot of people, in part because the correct "size" of steps or sub-problem can change from problem to problem and from language to language. This can absolutely be taught, though. Some students have an easier time of this than others, but eventually (in my experience) they all get there in the end, and develop an intuitive sense of how to do it... at which point 99% of people immediately "forget" what it was like to not be able to do it, and become incapable of recognizing and dealing with students who haven't gotten there yet. :-) Most programmers (myself included, at least until my dozenth or so student, at which point I figured out what was going on) fall into this category: thinking in this manner is so deeply imprinted into our cognitive processes that we typically have a very difficult time visualizing what it's like to not be there. We're sort of like fish and water, if you know what I mean.
The second problem is much more difficult to address. Abstraction is one of those things that, I'm convinced, some (most) people can "get" and others simply can't. For example, I've had students who seemed to understand arrays perfectly, including the idea of using an integer subscript to refer to the value at an array index such that if you showed them the following code:
myList = ['monkeys', 'elephants', 'giraffes'] print myList[1]
they'd easily tell you that it would print 'elephants' (yes, they can usually get their heads around zero-indexing without issues). If, however, you showed them this code:
myList = ['monkeys', 'elephants', 'giraffes'] idx = 1 print myList[idx]
a lot of them would be more than a little bit lost. Even worse would be if you showed them this code:
for i in [0, 1, 2] print myList[i]
They'd be really lost, then. Even if you walk through it line by line, with lots of extraneous print statements, there is a certain sub-type of (otherwise perfectly capable) student that just isn't gonna get it. I'm convinced that this problem--- lack of abstraction ability--- is also why so many students have problems with loops. Dealing with loop counter variables (and the things that you usually want to do with them--- array indexing, printing, doing math, etc.) is very hard if your brain isn't able to think in this abstract manner.
It's worse in Java than it is in Python, just 'cause there's so much more code involved (meaning that it's harder to pinpoint exactly where the confusion is coming from), but the problem totally persists even in sane teaching languages. I've talked to a lot of other CS educators who've noticed the same thing- no matter how you approach it, this level of abstraction is just beyond some students' reach. It gets worse once you try and teach them about object/class distinctions, and so on. It's not that they're stupid- my students are usually MDs working on their masters' degrees. It's just that some people's brains don't work that way. And it's not that they can't do other computer stuff- some of these students have gone on to become pretty good at SQL and even relational data modeling, which you'd think would use some of the same cognitive patterns, but apparently is different enough that it's doable.
I don't know if the problem would be better or worse teaching with a purely functional language; my gut says "worse," but I haven't tried it so I don't know, and the fact that many students with this problem go on to handle declarative languages pretty well gives me pause.