I've actually been thinking about creating a programming "quest" that gives you one very simple programming problem to start with after a basic introduction (modify this program so that it prints out the product not the sum), and the output of that program allows you to unlock later problems. This goes on, creating a chain learning effect. Once you get to a certain level the problem could be to write an implementation of a simple decryption program that's needed to unlock later problems.
I've had similar random thoughts ... Imagine a game, where the puzzle to pass to the next level involves writing a program to calculate something. The early problems could probably be solved mentally, so kids understand how their code relates to "the real world"... Then you could progress to problems that would be fairly difficult to calculate by hand. You could have quests, where you explore a world looking for clues. (it doesn't have to be 3D — 2D would suffice) Imagine a 2D dungeon game, where the books/scrolls/scrawled notes you pick up don't magically let you through doors, they just give you instructions that can be put together to make a program that will calculate the answer to a puzzle. Using Skyrim style games as a metaphor, the books and notes you find are usable code instructions, and the crafting or enchanting tables are code interpreters or text editors that let you create code to put through interpreters.
It sounds like you haven't seen my posts in the General Discussion and Projects Forums about the Pi-finity! 3-D educational game a number of software developers and I have been working on since February to help teach science, math, software development, and other technologies. The goals are very similar to what you're describing here, but, it will all be withing 3-D worlds to use the Pi system's very capable Graphics Processing Unit (GPU) and 1080p HDTV output via the Pi HDMI port.
Pi-finity! will actually be a system of games, with each world (represented as a real planet, both within our solar system, as well as elsewhere in the Milky Way galaxy) hosting one, or more, games, able to be populated by players with space/air/ground/water craft, space/land/water facilities, equipment, etc. Where the physical characteristics of a planet are known, they will dictate the behaviors of activities in the vicinity of the associated world. Where they aren't known, players will be able to create models with characteristics of their own design, using tools we will provide. Teaching software principles will be performed in conjunction with solving scientific, mathematical, and engineering problems, with a broad range of simplicity to difficulty in both the problems and the software needed to solve them (e.g., a few lines of source code, to entire applications).
None of us developers has a Pi board yet, but, I am accessing one in the UK remotely from California to start trying out ideas. Once we all have boards, it will be a few months before we have even an alpha version of the first few game tools working, and some example games built with them. So, it will probably be the Fall before people outside the development team will be able to start trying Pi-finity! out in a beta test. Just do a search on Pi-finity! here in the forums to see our discussions about what we're working on as we make progress.