I got a preowned iPhone 4 and activated it. Everything worked but cellular data. After resetting many different ways, using iTunes, *228, basically everything you've already seen in these forums, we still couldn't figure it out. I returned that phone and bought a brand new one. Activated it, same issue.
Finally, the 5th tech I spoke with noticed that I had a pending order to switch to the share everything plan at the start of my next bill cyle. Even though every other tech said that wouldn't make a difference, he took out the order and that allowed the phone to authenticate on Verizon's network and bam, issue solved.
So, he found that you can't activate a new phone with a pending order because the network won't allow it to authenticate with that order still pending.
Hope that helps someone else as I've seen this issue has affected several folks.