A Shaman's Spirit Animal is considered a native outsider, unlike a normal familiar. The Celestial Servant feat says that the animal companion/familiar/mount is now considered a magical beast. In this case, does the feat still change the Spirit Animal into a magical beast, even though flavor-wise it is much more logical for the creature to be considered an outsider with the feat applied?
There used to be a chart somewhere that showed what creature types trumped each other when multiple templates were applied. I'm pretty sure outsider trumps everything except undead. So even if a template added plant, animal, magical beast, etc, the final result would still be an outsider.