FOUND A FIX, and it has to do with profiles and APN's. I had this same problem after going from iphone 4 to a new 5S on verizon.
I had good cellular data only after doing factory resets, but would lose it as soon as I restored from my old backup.
So, what you have to do is:
Get connected via wifi, then open a web browser.
Go to: unlockit.co.nz. (I had my doubts, but saw other references to this working and at worst could just reset the phone again)
Click on the bottom middle button that says 'Create APN'.
Choose your provider from the dropdown.
Click "Install". You will now have cellular data back.
What it does is create a "cellullar profile" you can find under "Settings>General". I don't know what it does really, and contacted Apple for explanation. They said it is a carrier setting, so i will be following up with Verizon ASAP tomorrow (Monday) to make sure it is legit, but at least this gives me my data back, and shows an actual issue to pursue, whether or not this is the correct fix for it.