Argh, I had a long response written and I lost it. Short version - my DS7 started saying school was boring about 2 weeks after winter break in K last year. After asking lots of questions, we came to the conclusion that it was lack of physical activity during the school day more than anything else. Some parts of their school day *are* boring, but all kids can get bored in school, not just gifted ones, KWIM? You hear that word with a gifted child though and immediately start to wonder if your kid's getting enough challenge and if some other program would be a better place. Our school isn't the perfect fit, but after looking at lots of other schools, none of the others are perfect fits either.
I agree that going in and demanding something when you don't know what you're demanding is not such a great idea! I'd take a few weeks to ask your son questions after school, see how things are going socially, emotionally, and academically for him at school, volunteer in the classroom if you can to observe how his class functions, and try to figure out the true cause of his complaints. Once you can get a better understanding of what's causing them, you can determine what you might like changed, if anything, and then work as a partner (never guns blazing on the first approach!) with his teachers. The fact that he's going up to 2nd grade for math and reading means that this school is on your side! I'd think they'd be willing to work with you, once you have a better idea of what your son needs. If he's like mine, maybe what he needs more than anything is more recess, but we're more likely to get hit by an asteroid (or is it a meteor? DS is asleep, otherwise I'd ask him...) than have that happen at our school.