Sometimes its luck of the draw. I called several times about a problem with my wifes voicemail. Two times I got some very polite but unable to help (despite trying their best) people, who transferred me to another dept eventually. The third time however I got a guy who just ripped through the issue. I think the systems they use take some learning and if you get a person who has been there a while you stand a better chance of a solution.
That being said - still WAY ahead of sprint and AT&T - cant speak to verizon as I have never had them , but from what my brother tells me, they are no picnic either.