Part of the problem is that we usually teach in procedural style -- but this requires learning the MOST abstractions to do anything useful. Procedural style is based on variables, loops, conditionals, and side effects. Functional style is just based on function calls and conditionals; this makes it far easier to explain.

A larger part of the problem, I suspect, is that people are just not interested in the process of programming -- it's the product they want. The first thing you'll notice when you try to teach someone to program (in the normal case) is that they are focused to a fault on making the program work. This is the same problem that keeps people stuck to a single language: "well, it works." You need a genuine interest in the journey, not just the destination, to really be able to wrap your mind around the skill of programming. That's what gives someone the ability to intuitively understand how computers "work."

You wouldn't try to drive cross-continent if you're only interested in what's on the other side -- you'd just fly there, or take a train or bus or something. Likewise, if you're not interested in how a program does what it does, you should just pay someone who does care to do it.