Last year I wrote a simulator of a VERY simple computer. It had four instructions, 16 bytes of memory, and 2 registers. There were no branch instructions; literally the only thing you could do was write a program to add two (8-bit) numbers together. (And it would set the error bit if the result was bigger than 255.) I gave it an interface of nothing but (simulated) LED lights for the registers and memory, and then (simulated) push buttons to select a memory address and poke a value into it. It looked like a relic from 1956.
I then explained it to my then 9 and 11 year-old sons (who both are teaching themselves to program), explained base-2 math, explained how the "computer" worked and the four instructions they had available, gave them a whiteboard, and tasked them with writing a program to add two numbers.
They went NUTS! They were discussing theories, pointing out errors in each other's ideas, and getting excited when they fixed bugs. And they were doing it with a maturity level way beyond their years. They loved it. And I think that part of it was because it was simple enough that they felt in control of it. I also had the memory lights turn green as the instruction pointer advanced, so they could watch the program running. (It was slow enough that they could follow it and watch the registers change.) Granted, my boys love history, so that may have sweetened the deal for them a bit. But I was shocked at how easily they picked it up and how much they enjoyed it.
I'd like to expand it to the point where they can watch a stack operating, and see pointers and offsets getting used, but I just haven't had the time to follow up on it. But it confirms (for me) that the idea of starting at the beginning might be the most effective way to teach programming. (I also taught programming at a local trade college for a few years, and I noticed how much harder it was for the students to pick up--say--OO programming concepts when they had never had to deal with the problems that OO concepts were designed to solve. Trying to simplify it even more for elementary school students seemed mis-guided.)
The very best part of the story was six months later touring the Mercury Redstone program blockhouse at Kennedy Space Center (I know it's not technically on the KSC property, save your breath). They had an old Sperry-Rand computer with a console full of lights, and both boys lit up and told the (confused) tour guide "I KNOW THIS! I KNOW HOW TO PROGRAM IT!". It nearly brought a nerdy tear to my eye.
P.S. If anyone is curious for more information I'd be happy to share. It wasn't very complicated, but I think it has a lot of potential.