Yeah, there have been issues with the included OEM cable from the beginning. Don't know if they were ever fixed and there are still some old cables out there or if they are still being newly sent out with the same issues. For some reason Verizon folks seem to have more trouble with them than others. The cable should be the same for everyone though so maybe that's just a coincidence - or maybe the Verizon phones are just more sensitive to whatever is wrong with the cable.
The employees at the store the OP went to should have known about it and replaced the cable for her, but sadly they are often clueless. If the OP doesn't want to replace it herself, then I would suggest she call Verizon and ask for a new cable.