We started DS in kinder at 4.5 years against the initial advice of his preschool. Firstly they asked us to get him tested as they said he was unlike any child they had ever come across. When we gave them the psychologists report and advice they no longer said he shouldn't go to school early and came round to the idea. Our choice was made easier because DS really hated the second half of the year of preschool - despite loving it at the beginning of the year when he first started.
He is now at least one year younger that most of the kids in his class but still he is way ahead and very frustrated by this - he just doesn't understand why all the other kids just don't know what he does and why he is on a much higher reading level and maths level than anyone else. He also has problems socially and can't get the other kids to play his very involved rule-based fantasy games. His teacher has already suggested a trial grade skip after one term in kindergarten and by now he can manage it after spending a term getting his hand writing and "classroom manners" up to a decent level.
So I would start early if at all possible because your DS is going to need a lot of accereration one way or another and starting early is an easy way to get that acceleration going. Also bear in mind that these kiddos are quite unusual and early childhood teachers are very unlikely to be aware if their needs once they start formal school.
