A someone who knows a bit about robotics and electronics, I'd recommend the new Arduino Robot:
It has all the essentials you need to build pretty sophisticated robots; the Compass, IR Sensor, 360 degree turn on the spot, 2 micro-controllers, LCD, sensor ports distributed around.... it's a really well thought out, sound basis for robotics. Here's an interesting account of the story behind it:
As for the Lego Mindstorms ( I have one); it's good but basic and you're constrained by what your allowed to do. Put it this way... Mindstorms is the Apple iPad (polished and fancy) whilst Arduino Robot is your fav. Linux machine (very capable, expandable and gives you a sound basis on which to build).