I've had great experiences with Verizon and I've had stupidly ridiculous ones too. I usually call in most of the time and order online. Usually only go to the store if I'm buying the actual phone. Within like one minute of calling in I can figure out how well or how badly the call is going to go, based on their attitude and if they listen to me when I try to explain my situation. Usually the most difficult calls I've had are because I'm on my father's account, so they need his okay before they do ANYTHING, even tracking an order that I placed with MY OWN credit card, and is in no way associated with a plan change (like ordering a new charger or battery). They also can't issue a refund to my credit card without his permission, which is just stupid, but I digress.
I also hate their kiosk crap, especially the fact that, like you said, you have to give your number like 4 times before you can get actual help. I've noticed the employees are generally amicable, but do see a lot of them just standing around when there are lots of names in the kiosk queue. Most of the time the customers just need a point of sale to make a purchase and don't need to go through the rigamarole of pulling up account information. Blah.
Also, I'm pretty sure by 'new' the guy meant they'll send you a 'certified like new replacement'. I'm curious - was the replacement phone brand new, or was it a CLNR? If you're outside the 14 day return window but under warranty that's what you get. Maybe you're the exception to the standard? It irks me that they give you a CLNR instead of a brand new phone if you have problems. If you have any other product, like, say, a toaster, and it breaks under warranty you usually get a brand new toaster. I wouldn't even mind extending my contract out a bit if I got a brand new phone instead of somebody's refurbished one.
I do like their actual service, though. Verizon far and above out performs AT&T, Sprint, or TMobile in my area. Plus, I got in under the unlimited plan, so unless I'm on 3G and go over like 2GB and the cell tower is congested I don't have to worry about slow speeds. I leave 4G on all the time though, and they don't throttle that at all, so I'm set. For me, the really good cell service outweighs any of the customer service shortcomings, since I don't usually have problems. I've never had to have a phone replaced, and I've gotten phones from both Motorola, HTC, and Samsung.
Sorry for the long winded post