Clean you iPhone Dock port with a clean dry toothbrush. Try to charge again. If still problem, all Verizon iPhones still have Warranty Coverage, take iPhone to Apple for resolution of this problem.
If you want you could, use the toothbrush with a bit of Isopropyll Alcohol and clean again, especially the pins which are on top of the mid rib. Let it dry for a minute. Try to charge again.