Not sure about how FFXI was. But for FFXIV the reason for the QQing was because PLD was more difficult to use as a tank. Most of the complaining seemed to come from Warriors that were trying out Paladin. They realized that Warrior as it was, was so much easier to Tank with, and due to the complaining of it "sucking", many decent Paladins were left out of parties.
Now with the adjustments, forums, and practice, people are realizing Paladin and Warrior are both effective, and each slightly better in their own situations.
The complaining stems from good Paladins getting shafted in parties because of the mindset that Paladin sucks. Which is perfectly understandable, because why would a PUG take a chance that a PLD may not be good, when 9/10 WAR's get the job done.
I'm glad that's all in the wind now.