I'm with dpcan on this one. I started my current 10yo on Scratch at 8 and have been giving him incremental "challenges". The immediate feedback for even his first "program" was enough to keep him hooked. He regularly keeps making new games and often pushing the system to its limits (Scratch has many annoying limitations if you're a seasoned programmer or even a kid who has figured out that something like an array - he wouldn't use that word, tho - would be useful).

He started 5th grade last week and one of his classes is a programming class which uses MicroWorlds - http://www.microworlds.com/ - as the learning platform. I grabbed the demo and may shell out the $100 for the home version, just so he can do stuff here in it as well. It's not a horrible system, but it's definitely rough around the edges.

I fully expect to have him starting in Python by 6th grade, tho.