I realize that this is purely anecdotal, but may answer your question.
My father got me playing around with programming when I was very young -- I think six or eight years old. Some of my first memories involve our VIC-20 computer.
While a lot of what I did was just typing in simple programs from a book, I did some experimentation on my own, and it became pretty obvious how variables, loops, and the rest worked.
When I hit school I was mathematically so far ahead of everybody else, not because I'm some kind of genius, but because I had already spent a lot of time unknowingly learning algebra.
This was a disadvantage, because the school system wasn't built to cope with a kid that understood algebra before he had memorized the multiplication table.
As an adult, however, I've enjoyed a pretty serious advantage when it comes to understanding abstract concepts, especially anything involving symbolic manipulation, and I think I can thank that VIC-20 BASIC manual from many years ago for it.
I wouldn't be too worried about starting a kid out 'too soon', provided that other areas of the child's mental development aren't neglected in favor of developing mathematical skills.