"Could not activate cellular network" message

I just bought a lightly used iPhone 4 16 gig from a friend, and after two days of working perfectly fine, it stopped connecting to anything 3G related, including Safari, iMessage, and Internet-reliant apps, such as voxer, mail, and maps. I have checked with Verizon that the data plan is covering the phone, which it is, and it says 3G, but it will not connect to either 3G Internet or edge Internet. I've already tried both hard and soft resets, restarting, restoring to factory settings, and restoring from back-up, and nothing is working. The only thing I HAVEN'T done is take it to an apple store, but they're not exactly close!