I'd like to make a quick plug for Robot Turtles -- the board game for little programmers. This is a really fun game for 3-8 year olds that purports to instill the foundations of programming. I can confirm that it is a blast for that age range (and quite frankly, pretty fun for the oldsters, especially if you like performing in front of a captive audience). No idea if it instills programming, but it will surely prepare them for Roborally.
Note: I have worked for the founder, but not on Robot Turtles, and I do not have a financial relationship with either.
http://www.kickstarter.com/projects/danshapiro/robot-turtles-the-board-game-for-little-programmer