I'd really stick the paladin in with one of the shaman groups and stick to the 25 man concept.

Reason? Because with the shamans you have 16 totems for the pally... thats a LOT of wasted potential.