Hi there, I am currently employed by a k-12 school as an admin/all around support guy, and I have successfully introduced a linux lab this year...and they love it!
I'm not sure the amount of time that you or the people who would be doing the deployment are willing to invest in the project, but I created a very simple distro, with the intention of using cloud computing tactics on it. The students are using google docs/gmail/gcal and the spreadsheet and presentation tools google also offers. The kids love the lab because its fast and easy, the teachers love it because of how easy it is to share (that's all google however :P ) and the constant uptime, and the superintendent LOVES it for monetary reasons.
This lab was actually created with old crud machines, ones that would have been thrown away. The fact that it's now a fully functional place for teachers to bring students is really opening everyone's eyes. With the majority of k-12 kids just using the computer to type and get on the net, there really aren't compatibility issues (other labs are obviously still windows for speciality software).
I guess what I'm trying to say is, if you have some old machines lying around, try scratching an itch. Tell staff that you can pull a new lab out of thin air, and they won't have to fight to sign out the few available ones to have kids go in an type papers. You get the idea, it sounds corny, but its worked for me.
Anyhow, this lab has been a huge success, and I already have the go ahead for another, and very possibly single workstations for teachers rooms as well, I only hope that others can manage to do the same.