Read other letters about this article
I am probably of the last generation that actually started with a machine that you could easily program close to the hardware. When I was growing up, a C64 was already a bit long in the tooth, and Amiga 500 was all the rage. Even the A500 was already much more complex than its predecessors, and after that, it's just got more difficult to actually get a grasp of what programming, at its core, is all about.
The biggest problem these days is the huge barrier to entry posed by all the neccessary APIs you need to master before you can get anything done. Kids in particular need some instant gratification from their efforts, and it isn't happening if you need loads of boring broilerplate code just to display a window, let alone do anything with it.
I don't agree with your idea that the language needs to be BASIC, though. You can follow through an algorithm with pencil and paper while using a structured language, too, and I think structured languages start teaching good practices about dividing problems into smaller subproblems right off the bat. Python is probably a nice first language; Ruby is another, but the latter has has some peculiarities (blocks for example), which are nice for those who understand, but won't make for a good learning experience. The issue still remains that you aren't drawing pixels on screen easily... perhaps there should be some kind of a beginners' graphics library that one could call.
The academically minded side of my brain would like to suggest something daring in educating a youngster to appreciate computation for its own sake: use Scheme! It's an easy Lisp dialect, implementations of which are freely available. The syntax is minimal, and it encourages thinking about programming in terms of function evaluation. The Sussman book "Structure and Interpretation of Computer Programs" is a MIT course book and a great introduction to programming from the functional programming perspective, and seriously, I have a feeling that a bright kid would be able to learn the language reading that book...