This is what I did to fix mine....
Reset Network Settings
Please keep in mind that any Wireless Access Points and their passwords that you have on your phone will be erased and you will have to reconnect to each one of them again.
Hope it works for you
From a computer go to http://www.apple.com and if it has been an issue I would ask your question in the Apple Forum.
If the phone is not over a year old you could have it replaced under manufacturer warranty or within a certain number of days call tech support at apple before you call Verizon wireless.