I don't think you can start too soon. I started visiting kindergartens when my son was 3 1/2 and enrolled him when he was 3 3/4. He didn't actually start school until he was 4 1/2, but by enrolling early, we locked in a great tuition rate that we now get to carry through until middle school.
That said, it did seem early and kind of crazy at the time, and even now I had to check myself to make sure I have things straight. In hindsight, I can see why the public school thought I was loony for inquiring about kindergarten for a 3 year old, but it was the absolute right thing to do.
