Our 4-player 25 point buy group consistsof a Ranger, Bard, Fighter and Cleric. We used special house rules (since we started with only 3 players) giving us all +2 skill points and 2 bonus class skills (and a extra ability, like Fearless level/minutes per day). We are near the end of the Campaign.
So far I can tell you: Having a Bard is great. He is an extreme force multiplier. With the Ranger and the Fighter we had two characters that benefited from this ability greatly.
The Bard basically adds at least between 5% to 15 % to the average damage of the group by just spending one action (starting Inspire Courage) during the whole combat. On top of that, he fires spells like Haste or Rage to buff us even further.
Aside from that, most magic items go directly to him (unless the Cleric or Ranger can use them) - with a maxed Use Magic Device (at least I think it is maxed, maybe he doesn't need to

) it is quite effective.
Extra Music and especially Lingering Song are vital for him - start singing once, the effects last the whole combat, and he can concentrate on using the occassional Bard spell or one of his magic items.
He rarely engages in melee or ranged combat and concentrates on using spells and magic items.
He later picked up Leadership to add some Combat Power to the group (a Barbarian cohort).
In your group, the Bard would probably directly boost the Fighter, Barbarian and the Rogue in combat, and (once buffed) the Cleric. I think a Bard will be a vital asset. A further melee warrior (like a Paladin) won't add much, and the various meelees would just step on each others toes (quite literally).
That said, if you usually enjoy playing a melee fighter (or even a Paladin especially), that might be a nice choice. If you love Clerics, a further Cleric never hurts (but ensure that you two have sufficient different Gods and Domains - this allows for more versatiliy of the group and for a clearer distinction between you two).
Obviously, a Bard will also be useful in all non-combat situations. Bardic Knowledge (or the new PHB II Bardic Jack-of-all-Trades-Feature-what-was-its-name) should also be very useful. The social skills will work a lot better with the Bard than the Paladin (Paladin has only Diplomacy and Sense Motive, but a bard can also pick up Bluff, Gather Information and Knowledge (Local), which will also aid in non-straight-forward or honest dealings

)
Oh, and don't waste skill points on multiple Perform skills - Singing is enough.

(I believe the Complete Adventurer also offers the Feat Versatile Performer, allowing you to spread your perform skill for other instruments)