Full disclosure: I'm one of the guys who invented Kid's Programming Language, which is now http://www.Phrogram.com, which others have recommended here. Let me add some programmer-oriented info about it.
It's a code IDE, rather than drag-and-drop, or designer-based. This was intentional on our part - we wanted to make it easy and fun to do real text-based programming, particularly programming games and graphics. This is a fundamental difference between us and Alice and Scratch. Which you pick is a matter of the kid, their age and aptitudes, your goals. Using them serially with the same beginner might be a great way to go - if you do that, I would recommend Scratch, Alice, Phrogram as the order. Phrogram has worked best for 12 years and up, but I know dads with 6 year olds who have taught their kids with it, and I know 10 year olds who have taught themselves with it.
The language is as much like English as we could make it, and is as minimal as we could make it. The secret sauce is in the class-based object heirarchy, which is again as simple, intuitive and English-like as we could make it. The object heirarchy is optimized for games and graphics. 3D models are available, and 2D sprites. Absolute movement using screen coordinates is supported, or relative movement ala LOGO turtles - Forward(x), TurnLeft(y).
The IDE comes with over 100 examples, some language examples (loops), some learning examples (arrays), some fully-functional games and sims (Pong, Missile Command, Game of Life).
To give you a sense of how highly leveraged we made the language and the IDE: with 27 instructions you can fly a 3D spaceship model around a 3D skybox, using your keyboard. The same with a 2D sprite is 12 to 15 instructions.
We are working on a Blade-compatible release of Phrogram that will allow programs to run on the XBox 360. Yeah, the XBox, on your big TV. Nice motivator for getting a kid started? :)
Phrogram includes support for class-based programming, with methods and properties - but that's only encapsulation, not inheritance or polymorphism.
A tutorial and user guide is available,
My own ebook is available at Amazon and other places online, "Learn to Program with Phrogram!," and gets a beginner started by programming the classic Pong.
Phrogram Programming for the Absolute Beginner, by Jerry Lee Ford, Jr., is also available, as a paperback, at Amazon and elsewhere.