Sorry, I meant in parallel (?), with all the anodes and cathodes in line with each other all connected to the same outs from the Arduino.
No, if you connect them in parallel they need a resistor in each cathode (assuming common anode).
The LEDs are always on, but change colors together.
If they are always on they can't change colour. It sounds like you want to be able to dim them as just on / off control will only give you 7 different colours. In which case your port expander options are a bit limited. You see 25 RGB LEDs is the same as controlling 25 * 3 = 75 LEDs which is quite a lot to wire up. Simplest would be to use five TLC5940 chips chained together, although that has it's challenges:-http://www.arduino.cc/playground/Learning/TLC5940
You will need supply decoupling on each chip:-http://www.thebox.myzen.co.uk/Tutorial/De-coupling.html
This is probably where I'm most worried.
Yep me too.
Can I connect them in clusters to a wall wart like this one (12dcv 600mA)
Well no. You would be:-
1) Feeding them with too much voltage
2) Each servo could take 600mA so you might need one wall wart per servo.
It is vital you make measurements of your servos so you can plan this. You will probably need voltage regulator(s) to cut the voltage down from your wall wart to what you need.
This is scaling up in a grand manor and that brings it's own difficulties. Start off with just one at first.
12 all do the same thing and 13 do all the same thing.
So that is basically 6 different control circuits. Yes you could probably drive those from one TLC5940 and six logic level p-channel FETs.