I just switched tonight from an ATT iphone 4 to the Verizon iphone 5.
I made a backup of my ATT phone using Itunes and restored that to the new iphone 5.
After restore cellular data no longer works on my Verizon iPhone 5.
I have been able to duplicate and confirm the issue by erasing all content, activating the phone, test working cellular data, then restoring the backup again and losing cellular data. I can assure you that all options to disable 3G/cellular data are correct both before and after the restore.
I also have a ticket in for signal issues. My phone will get stuck in 1x mode even though the signal should be 3g as 3g signal worked in the same spot mins before. Once again something I can replicate.
I suspect the phone needs a modem update or the network needs an update in order work with the new iphone 5 modem.