You have a fairly well balanced party to begin with, so let's take a look.
Tank: 1-1.5 (Paladin, possible Bard)
DPR: 1.5-3 (Sorcerer, partial to full Paladin, partial to full Rogue)
Skills: 2.5-3 (Rogue, Bard, partial to full Ranger)
Utility: 1-1.5 (Bard, possible Sorcerer)
Melee: 1-3 (Paladin, possible Rogue, possible Bard)
Ranged: 1-3 (Ranger, possible Rogue, possible Bard)
Melee and Ranged looks balanced, based on what little we know. However, Bards are mediocre tanks at best, and Rogues seldom succeed as a tank. DPR has a lot of potential, based on the character builds. The skills should be solid at a minimum, probably excellent. Not much utility however, with pretty much only the Bard and maybe some help from the Sorcerer.
Given this, I think the Cleric is the better option from a completely neutral standpoint (if one inspires you more than the other, play that!). The barbarian will provide more DPR to a high DPR group, while mediocre AC will cause you to soak up a lot of the Bard's spells for healing (even after Rage). A Cleric will provide improved utility, and several domains provide Heavy Armor Proficiency. Both will fill the weaknesses of the group. In addition, extra healing is never a bad thing, and will open up the Paladin's spell slots for Smite.