My day job is in a school, and over the past few years I've seen or taught (or attempted to teach) various children, in various numbers, programming lessons.
Children are all different - some are quick learners, some aren't. In particular, some have better literacy skills than others, and that definitely makes a difference to the speed at which they'll pick up programming. I bet that most of us here, as professional computer programmers and the kind of people who read and post to forums for fun, learnt to read at a pretty young age. For those kinds of children, and if it's your own child who you can teach one-on-one, you could do worse than JavaScript - it has the advantage that you can do real stuff with it right away, and the edit-test cycle is simply hitting "refresh" in the browser. It gets confusing when you start to run in to how JavaScript does everything asynchronously, and is tricky to debug, but for a bright child under close tuition these problems can be overcome.
LEGO Mindstorms is definitely up there at the top of the list. Most schools now super-glue the bricks together to create pre-made models that can't have bits nicked off of them, but this shouldn't be a problem at home. Over on the Times Educational Supplement site (website forum for the UK's weekly teaching newspaper), the "what programming language is best for children?" topic comes up pretty regularly. Lots of recommendations over there for Scratch as an alternative to Mindstorms - bit more freedom than Mindstorms, again probably better for the brighter student who could also be given a soldering iron.
I've found that slower pupils can still have problems with Mindstorms, even though the programming environment is "graphical" - there's still a lot going on on screen, and there's a fair bit to remember (this was an older version, mind - haven't tried the snazzy new one yet). In my experience, the best all-round introduction to programming is probably still LOGO - actually a considerably more powerful language than most people give it credit for. The original Mindstorms book by Seymour Papert (nothing to do with LEGO - they nicked the title of the book for their product), one of the originators of LOGO, is the canonical reference for teaching programming to children as a "thinking skill" and for the concept of Constructionism in learning.
We've had classes of 7 or 8 year-olds programming LOGO. Note that we aren't aiming to make them "software developers", that's a career path they can decide on at some point post-16. At a young age we're trying to get them to think of "computer programming" as just another tool - how to set out a problem to be solved by a computer, in the same way they might use a mind map to help them organise and remember stuff for an exam. No poor child should be sat down and drilled in the minutia and use of a particular language, they should be left to explore and figure stuff out as they like.