iPhone 4, Verizon, "Could not activate Cellular Data Network"

Ugh..

I had to switch back over to my iphone 4, on Verizon. So, I didn't have a wifi connection yet, so going to the app store, it pops up that there isn't any cellular data connection. Says, "Could not activate cellular data network". It shows the 3G icon at the top. I went to Settings > Network and Cellular Data is ON. I've never had that before.

I've turned it on airplane mode for a few mins, then turned that off, still no go. I rebooted the phone, no go. I'm lost.

Ended up going through a decent amount of troubleshooting.

I turned on/off airplane mode.
Turned off data service, turned back on.
Reset Network settings
Soft reset
hard reset

at the end, I did a complete wipe. Ok, so I have the phone JB, and forgot to NOT erase all settings and content.

Well, so the phone turns off, goes into restart, and the circular "busy" icon turns and turns for about ten minutes. I went ahead and held power + home button until the phone restarts. Apple logo comes on screen, and within a few mins the phone has restarted. All icons, etc., are there like there wasn't any content erased. Also, it gave me the activation message. A couple mins later, everything is working 100% again.