I started programming an old Tandy Radio Shack TRS-80 back in 1980 (I was 12 or so). I learnt MS Basic (written out of a garage by a young Bill Gates), and had a blast.
I used to get the books with the source code for games all typed up, and copy them into the old "Trash-80".
I had to learn to debug, as sometimes the code in the books had typos. It was invaluable training, and I learn't how to program in Basic, moving on briefly to machine language, and eventually working in multimedia (Don't you love industries which climb to giddy heights and then dip to dramatic lows?)
These days, kids have all had a much higher level of exposure to computers than I had back then, so the learning curve isn't necessarily as steep.
I agree with bblank, Basic is dead (sad to say), and it can teach some bad habits. But the same can be said for any language you learn with an intention to move on to another language later.
noperf, I would probably reccomend something like Macromedia Director (I think it's still owned by Macromedia??)
This is a self contained multimedia authoring tool (you can use it to put together anything from a piece of simple animation, or a game, to a complete interactive corporate CD-ROM application).
It's relatively easy to get started with, as it has an extensive level of control through its' GUI (Graphical User Interface - AKA press a button, and something happens, instead of having to write out a line of code to do something simple).
It also has a fairly powerful scripting language called "Lingo", which adds a level of power to this software, and is fairly easy to grab onto. If you want to go further, you can embed scripts in C++ etc. for added functionality.
The beauty of this software is that you have all the whizz-bang features that kids love (pretty colours, flashing lights, sound etc), but it will also teach the young 'un some solid basics in computer programming with a fourth generation, object oriented language.
Another piece I might reccomend, although it is much more basic than Director, is Flash, also by Macromedia. This is predominantly for 2D animation, but people have programmed games as well, and it is very easy to learn. I've even seen free copies on magazine cover CD's occassionally. Maybe start with Flash, and work up to Director?
All the best, send me a copy of the youngsters first game!
Louie T. Fly