I was learning C when I was six years old. Definitely helped that my older brother (then 11) was the one teaching me— I wonder if having young children learn from older children might be good advice in general?
I remember there was one other kid in my year at school who was better at C than me at the time, so I don't think I was that unusual.
I think it easy to underestimate what kids are capable of.
The OP has it right -- if you're doing something you want (building a Dr Who game, changing your high score, turning all the baddies into strawberries, making a spider run around the screen to scare your mum) that's the best, dare I say only, way to learn.
Having said this, nobody at my school could program at all (despite the BBC's best efforts). I didn't learn "real" programming until university; web scripting and PHP before that. Maybe that's why I'm such a hacky coder even now.