@Polly - great post, it is very clarifying!

We had mild to moderate boredom issues with dd in preschool.

At age 'almost 3' she was in a classroom she could not stand, I could not figure out why but after a couple weeks I finally asked to have her moved. The other option was a 3/4 class, with mostly 3's. This was so much better for her. At the time I rationalized it was better because she had been able to exercise some power over the situation (?)
Much later in the year, I think the boredom struck again, she was often 'sick to her stomach' or made similar stalling excuses/complaints to keep from going in. Finally when she just declared it was too boring and 'all they do is play', I thought I'd better investigate further. I knew already she was a smart one, but after discussing with the director what to do, and getting some testing done I was able to get her shoe-horned into K when she was 4.5, and we are still on that track, considering first grade at 5.5 in the public school.

We are lucky the classrooms at the preschool were mixed-age, and the school is pretty great in general, or I am sure it would have been much more problematic.