An old math teacher friend of mine has introduced his 7th grade students to "programming" through Lego Mindstorms. The kids work in teams to build the robots from kits and then program them to navigate a maze/obstacle course using Lego's software. I don't think its that close to "real" programming, but it does get the kids thinking about how to break down problems into logical steps. And it's enough like play that pretty much everyone gets into it, and the ubernerds in the group race to see who can finish the course in the best time.

I'd like to see more things like this happen in schools, but it's hard to find the time and money for ~10 mindstorms kits in every classroom.