Become a MacRumors Supporter for $50/year with no ads, ability to filter front page stories, and private forums.
Toggling the voice roaming seemed to fix the trick.
I also know if you reset all settings on the device (but keep data/apps) that it will fix the issue also.
 
I JB my friends verizon and had this problem after installing an app, but we just toggled the airplane mode and the signal came back.
 
Register on MacRumors! This sidebar will go away, and you'll see fewer ads.