I believe WotC as even admitted that the cleric may look a bit "too good" on paper.
But, in function, the cleric rarely gets to shine in anything other than making the other members of the party feel good. For as much of a machine the Cleric can be if he buffs himself up, imagine how much GREATER is the threat of buffing up the local fighter, barbarian, or paladin? The vast majority of a cleric's spells are protective, buffing, or curative, and so they're not going to get much of a chance to lay the smack down themselves. The domain powers are semi-crap. Even a cleric with the Magic domain will be shown up by a wizard (so why bother being a second-rate wizard?), and a cleric with the Strength and War domains will still not be as effective a fighter as the Fighter (so why bother being a second-rate fighter?). And some...whoop-dee-doo, really, to much of 'em, which come into play about as often as a Ranger's favored enemy.
The cleric gets a LOT of goodies, true. But it's still not a popular class, and thus it doesn't pass the "if it's chosen all the time, it's too powerful" argument, because it's NOT chosen all the time because the thing it's powerful AT is in making everybody else better. And in a game like D&D, everyone wants to be the enemy-bashing heroes. It's hard to play the "glue" that holds the party together.
Even a cleric that focuses on blowin' stuff up won't be as good at it as a wizard. An NPC cleric has a bit of an advantage there, because they usually don't have a party to buff and/or heal, and so can devote all of their magic to blowin' stuff up, but even then a Wizard will outshine the cleric in terms of how often and how potent their blow-ups are.
Think about it. Flame Strike is about equivalent to a potent Fireball...and a wizard of the same level can be hasted, throw out two of 'em, and probably metamagic them so that they're more potent than normal anyway. A cleric's boom spells are for when they don't have to heal or buff.
I mean, take a look at the White Mage on FFd20 for evidence -- that class has *all* the possible blow-ups taken away, and their healing enhanced, and nobody who's played one yet has thought the class was anything other than weak. Even though they often outshine the cleric alone in times of healing and buffing, and are still no slouch in the BAB/HD category...
Being able to blow crap up goes a LONG way toward making a class playable. And Clerics, for all their "perks," generally can't blow stuff up as good as ANY of the other classes, especially when you consider that those other classes would normally be buffed by the cleric...because why be a second rate anything when you can make your first rate something even better? (unless something tragic happens to your first rate -- in which case, the cleric's powers as a second-line whatever come into play).