amy..I have been having cellular issues lately and got on the phone with verizon and insisted on talking to a technician. I was able to tell him that I had been changed to a different PRL and that my service had degraded. He offered to push through a different PRL (a hybrid) and I do think it's helped. In addition, I had been having battery issues since the ios6 update, but I think the new PRL has helped that...still to be determined.
See if you can get back on the phone with Verizon on a land line and insist on getting through to a service tech. Ask them to push through a different PRL.
(btw, PRL is "Preferred Roaming List")