The problem (probably) isn't only because it's too small, wiring can be hard to understand.
I think this might be a solution:

It'll cost you some work. But it will get difficult for them to wire it wrongly.
Also, I believe coloring them, will make the kids understand it much better. This way they would also be less likely to short out pins etc. Saving you some rangers/arduinos.
Be sure that the power-connectors are not reversible. And you should use a separated supply (with overcurrent protection and what not) and tie the GND to the arduino GND. This way you could even use the supply power for heavier devices.
I'm not a 100% sure on the resistors though, they might interfere with some things you want to make/show.
Maybe even add blue color for inputs and yellow for outputs (or whatever the standard is). Or you might even make generic connectors, like on the Lego NXT robots, that's some really easy wiring! http://www.philohome.com/nxtldraw/NXTkitLDview.jpg
Or check out projects like: "LittleBits Arduino".
https://s3.amazonaws.com/lb-spree/spree/products/2003/large/ArduinoDetail4.png?1423167488
And, check http://www.rugged-circuits.com/ruggeduino/ on 10-ways to destroy your arduino. If you take these things into mind, you can make a pretty solid Arduino, so that wrong wiring won't lead to any damaged Arduino's etc.