I was just reading a slashdot article on Robotics for Kids
and read a particular /.'rs comment that really sounded great!
...it is fun to PLAY robot. Explain the concept that robots only do exactly what you say, and then make some "commands" like "move forward", "turn left", "pick up object" and then work together to try to solve problems, like "how can we get the rubber snake into your sister's bed?". The kid plays the role of the programmer, the CPU, the robot motor (we use toy dump trucks typically for this), and the all-important role of the debugger.
Such a simple, cool idea! I can't wait for my kid to get out of school tomorrow and give this a try!