First off, I personally think clerics rock hard, but my players seem to usually have a much different viewpoint. I guess it mostly boils down to clerics being viewed as a rather boring, un-exciting class to play. Why that stereotype exists is probably a combination of multiple factors.
A ) Cleric = healer. This is a standard view, and many players feel being reduced to a healer role is boring. Of course you can play a different style cleric, but people complain when the cleric can't heal.
B ) Sub-par at dealing damage. I personally disagree with this sentiment, but it seems to be a common view. Obviously spells can enhance the cleric quite a bit, but they usually aren't as spectacular at dishing out the pain compaired to fighters or wizards.
C ) Forced to obey a god. This is quite campaign specific, but all your power is derived from some higher being so they potentially have some say in what you do.
D ) In 3e/3.5, limited feats & skills. Many players see feats and skills as ways to tailor/specialize or otherwise make a cool character, and the cleric seems much more limited in that regard.
I'm sure there's a few others I'm forgetting. I often find getting someone to play a cleric is difficult. When the players are selecting characters, the cleric is like that ugly, shrimpy kid that no one wants to pick for their team, and invariably gets picked last. I often have to find some other incentive to get someone to play one, which is frustrating.