I have the exact same issue. I live in a 3G Extended Network area. Data on Droid X worked fine. Got Galaxy Nexus knowing I wouldn't have 4G (3G has been perfect for me). I was out of town when I got it in a Verizon Network. Drove home and...well...no data on Galaxy Nexus. Told Verizon tier 2, and they said it was a "known issue". I've flashed all radios and combinations and nothing has worked yet.