Mindstorms absolutely Rock!! I got the original version for a Christmas + Birthday present when they first came out and I created a butler robot that would track a line of black electrical tape that was on the floor and you could put four cans of pop on it and when it was empty, it would hustle its way back to home base for a refill. I used it at a couple of parties that I threw while the parents were away back in high school and everyone thought it was cool.....it was a small step for robotics, one giant leap for nerdiness! Ahh the memories...
Anyways, I don't have any more suggestions for robotic hardware, but I do have a couple for programming robots that might be age appropriate:
First, "ALICE"( www.alice.org
) is a free software tool that helps teach a multitude of programming languages through interaction with 3D characters. It was developed in conjunction with Carnegie Mellon and was targeted to teach programming to everyone grade school and up. This software works very well at motivating students to learn and demonstrating how different commands can alter the outcome of the code. I see this as a great starting point for familiarizing the kids with programming while hardware is being scrounged up,and they are still in the stages of designing the robot.
The second tool that will help greatly is Microsoft's Robotics Studio.( http://msdn.microsoft.com/en-us/robotics/default.aspx
) This software is also free and can interface with a majority of robotic controllers(Mindstorms included). The software allows for the testing of code through the use of virtual robots and when the time comes to program the robot itself, the code can be sent relatively easy to the robotics controller.