I am also a fan of mindstorms, as many others replying in this thread, but I have seen that kids tend to "get stuck" simply building Lego... With motors and whatever of course, but the actual programming part has become parenthetical and very simplistic.
There is nothing wrong with that, of course! I have recommended mindstorms as a xmas present just a few days ago, but if you are really looking at teaching programming, then you will have to work a little extra to make the kids focus on the programming part.
Squeak is quite similar to the mindstorms programming environment, all graphical, and the kids will have a blast.
So, buy the kids Lego Mindstorms for christmas and use Squeak for teaching programming...