I chose the paladin and monk would have been my second choice.
Paladins are great from a role-playing perspective and can make decent tanks. The problem is that their primary ability is really great saves and a warhorse that doesn't instantly die at higher levels. A paladin with incredible stats or who takes all of the mounted combat feats and cons the DM into giving him some kind of half-celestial mount can be quite fearsome. Even more so, if the paladin shares all his buffs with the mount. However, depart significantly from that model (or don't have enough room to do your spirited charges) and the paladin seems like he's sucking air except on the attacks where he gets to smite--then he's as effective as a real fighter or a raging barbarian...on two to five attacks per day. Still, even such a paladin will usually be subject to the "wow, we get a great equine fighter we can summon once per day and a paladin comes with him too" complaint.
Monks can be very effective too. However, they suffer from the same problem as paladins. They need very great stats to be effective (a previous post that said, "try to get an 18 in wisdom and dexterity" indicates this--that's 32 points right there and the monk hasn't even gotten a strength or constitution score yet (both of which need to be decent if he's to be effective). I've seen very effective high strength half-orc monks but in general, monks seem to be weak.
All of those who picked druid are smoking crack. Seriously, druids are good at every level. If they didn't get animal companions, they'd be as good as clerics and nearly as good as wizards in the offensive magic department (in fact, stripping out the animal companion and nature abilities, I've seriously considered using the druid as a "wizard" in a non-standard D&D campaign--their abilities fit more in line with the wizards of myth and legend anyway). SNA is absolutely disgusting and wild shape makes druids excellent fighters or perfect spies. If you allow the Complete Divine spells (Nature's Favor, etc), no class can compare to druids in power.
Sorcerors suck at low levels. By the time they hit 4th level, a sorceror starts to get interesting. If versatility is still a problem at high levels, then you just designed a weak sorceror. At high levels, a sorceror has enough spells per day that she can be prepared for nearly any eventuality even without scrolls. Add in a haversack and some scrolls of the useful spell she doesn't know and she's easily the equal of a wizard.
Rogues are quite effective too. They're weak against undead, plants, and constructs but their sneak attack and uncanny dodge abilities are very useful. And their high level abilities (opportunist, the one that deals strength damage, etc) are very useful. They're probably next after monks on the weak list though.
Bards can be very effective if played properly. As others have pointed out, it's just as possible to build a melee bard as a melee cleric. And if you accept that your role in the party is supporting the other characters rather than being the star of the show, a good bard can make the difference between an APL 12 party defeating a fiendish razor boar of legend and that party having their butts handed to them. Haste, +3/+3 bardsong, displacement, Inspire Greatness, etc, all add up to a great addition to the party. Perhaps none of those (except inspire courage and inspire greatness) are things that couldn't be done by other characters but having all of those options makes the rest of the party much more effective.