Little Big Planet is an excellent example because it contains a level editor with enough logic to do things like this: http://www.youtube.com/watch?g.....-2-vdNItoI
I think it is this sort of environment that is needed to engage today's generation in programming, but with proper tutorials and a proper language to learn.
I arrived myself at a similar conclusion - assuming simple feats of programming (re:PRINT "Hello World", bouncing ball etc.) aren't interesting/cool enough to hold attention of kids today (I did say assuming...), while stuff that would being simply way too complicated, what if there would be a way to entice them with the real deal, then let them in through the back door without "paying the price of admission"?
More specifically, what if we could present them with a game at something at least vaguely comparable to today's standards (be it Abuse/Wolfenstein/Doom/Duke Nukem/Quake - hey, Angry Birds for all I care...), but crucially, a game that uses some kind of scripting on its back end to set up the playing field / control the opponents / etc. - a standard language like Python would be great, but I have no idea what is actually being used for such stuff. It might be a good idea to seriously dumb down said scripts, therefore making the game somewhat broken, perhaps much too easy. Kids then could get the 2D/3D bling that might keep them interested and the opportunity to get knee-deep into the scripts governing the game, trying to make it smarter / fix the targeting / path-finding of the opponents etc. without having to deal with the complexity required to program an actual real-life game. Which is not to say they wouldn't be welcome to pick apart the 3D engine in C later if they wish, but I'm talking about getting them interested at first here, at the entry level.
I mean, all you need is an Angry Birds (ok, Qbasic Gorrila...) clone that can initially only shoot straight, a level that requires a curved trajectory to succeed, and a short description of the relevant ballistics and we're in business, right...?
Am I making any sense...?