Way before I learned any real programming (well, maybe I had a little Basic at that point), I had software that was puzzles with logic gates (you have some number of inputs w/ different patterns on the left wall, connect up the logic gates to make the desired output on the right).
Today's modern equivalent is SpaceChem. And we've had plenty of games that teach you to break down problems into smaller parts
Maybe it doesn't teach you how to write a faster sort routine... but c'mon, these days most programmers have never seen a line of assembly, much less written one. They get by in high level languages like Ruby and Python, where they don't even have to worry about garbage collection or pointer addition.
You get the kids interested by giving them tools to make something that they can play with
Some are going to be satisfied with that
Of course, my only concern with this approach is that you risk having some people take a profession for granted -- the "I made a webpage for my club in highschool using GeoCities... why do we need to hire a professional to make out website?" type people.