From early this morning, my iPhone 4 would not lock onto the 3g service... indicating "Verizon O" or "Extended O" only, and barely able to get a simple webpage downloaded. I finally found a discussion about a similar issue - generally on the iPhone 3g, which suggested reinstalling Mobile Substrate form Cydia. I managed to get Cydia loaded and after a few tries, was also able to get Mobile Substrate reinstalled. And that did seem to do the trick. I'm so thankful that I didn't first try several other suggestions, most of which involved restoring, re-jailbreaking, and other rather complicated sounding attempts to fix this. I might note that it's difficult to make a Google search about the Verizon 3g CDMA data service. I kept getting back results that involved the iPhone 3g and iPhone 3gs.