Doc pointed me at David Scott Williams' DustyScript idea.
I sent him a brief email saying I thought it was missing the point, and suggesting existing software tools, but made a hash of describing the point, so I'll try again here.
Being a good programmer is not about the language you use, it is about the way you think, and the way you approach problems. You need to be able to keep high-level and low level goals in mind at once, to analyse and model situations, to express the model in rules, and to adapt the rules to new situations. Its perfectly possibel to write good clear code in almost any language, just as you can write bad, unclear code in any language or even 4 at once
Young children are fantastically good at learning languages by example, but often not good at predicate logic or deductive reasoning, which takes a lot of training. (As an aside, the book Reading Reflex applies this insight to teaching reading - instead of teaching deductive rules parrot fashion, it groups different representations of the same sound and gets the children to work through them until they derive an unconscious model that way).
The best 'programming' exercise with small children is the 'I am a robot' game. You play their robot slave, and do what you are told, but very literally, and in small stages, with 'error messages' returned in a robot voice. Just getting you to walk from the sofa to the bedroom can take ages and they love it. They naturally want to be the simple-minded robot too (just make sure they don't get too attached to it, or they may end up working in telephone support).
I've seen a huge amount of 'educational' software - I used to work in the CD-ROM business, and I buy up remaindered CD's from Marshalls for my 2 boys and watch how they use them. Most of them are dross, with the same few ideas (Pelmanism, missing words etc.) recycled with a different character or brand attached. Some have genuine insight, and I can see them learning to reason using them. Here are a selection:
Logical Journey of the Zoombinis is a wonderful introduction to deductive logic through a compelling game. It was designed with this in mind and my boys have been playing this since they were 3, and are still enjoying it now at 5 and 7 (as do I).
The Pajama Sam series of adventures from Humongous are good at teaching the global/local focus, but one that is great fun and teaches valuable debugging skills is Pajama Sam's SockWorks which features a long series of machines that have socks in them that you have to get into the right coloured baskets. As you can also build your own puzzles, the idea of solvable and unsolvable problems naturally comes up.
Zap! is another great game that teaches by stealth. You have to help 3 wisecracking cartoon charcters to fix their electrical, optical and audio-visual gadgets to get their show on the road. It manages to include a compelte circuit simulator, an optical workbench simulator and sound environment simulator, and still be lots of fun for Kindergarten children.
To teach programming concepts without writing textual code, Cocoa is perfect (if you have a Mac). It is a tool that enables you to create 2d video games by drawing the characters and defining what happens when they encounter each other by example. Andrew has made about 65 games with this, some original, some homages to TV programs or his brother's films.
Finally, if you want a comprehensible textual language, use Runtime Revolution, whose language Transcript is based on the old Apple HyperCard language, and as such has completely human-readable programs. This is what I plan to get Andrew into next.