There were three Paladins fielded this game. One extended deep into enemy territory with very little support and died to fleas and an opposing Paladin. The other two died to Ultimatums after their support units had died, which was also after fights where they'd done a lot of damage. Even then, one assassination attempt with an Ultimatum and Widows died because, even though the Ultimatum's screen of fleas had gone off to fight Minotaurs, the Paladin had a Lobster nearby.

This seems to be a case of careful and skillful Ultimatums doing their jobs rather than Paladin being defective.