After months of wondering and looking around for answers, we think we've finally found out why all of Verizon's 4G LTE phones (and modems / USB dongles) are having data connectivity issues, and it's a wee-bit technical even for us, but we'll do our best. This information has been gathered from various comments and forums across the net, so, take us at our word here.
When Verizon launched its LTE network in November of 2010, it was the first time the carrier had utilized a GSM-based (WCDMA, as opposed to CDMA2000) network in the United States. All Verizon phones and data-enabled devices had previously run on CDMA2000 connections - the network responsible for Verizon's 3G and 2G data. CDMA2000 uses an older authentication system (identifying and OK'ing your device to connect to the data network). Verizon's new 4G LTE network uses a newer, different, and more robust scheme to authenticate devices.
So, in an attempt to smooth out the transition to the new technology (Verizon intends to decommission its 3G network in most areas eventually) and ensure handsets used uniform schemes to connect to any part of the data network, Verizon essentially made it a network directive that all 4G LTE devices would use a single authentication system for both 3G and 4G data connectivity. They did this by requiring all 4G devices use UICC SIM cards, which allow for authentication on many types of networks.
This is what your 4G LTE UICC SIM card does - it's responsible for authenticating you on both Verizon's 3G and 4G networks. Verizon 3G-only phones use the old authentication system, because they don't have these SIM cards. Verizon is the only carrier in the US currently operating on this somewhat odd mixture of authentication schemes and network technologies. This means there are now millions of devices connecting to Verizon's 3G network using an authentication scheme Verizon hasn't previously utilized on that network, and (major) hiccups are occurring as a result.
The "hiccups" are authentication failures - the new scheme is extremely particular about failed attempts to authenticate a device. Your device authenticates regularly, "checking in" with the network to ensure you're still supposed to be connected. When your device fails to authenticate on the network (for any reason - and there are a gamut of possibilities), Verizon will kick you off the data side (not voice, though), either 3G or 4G. At this point, you notice you no longer have a data connection, and throw your phone at the nearest wall.
The severity of the problem can depend on your device. Some devices are more likely to re-attempt authentication immediately, and ten or fifteen seconds later, you're good to go. Some won't - and have to be forced to re-authenticate by switching in and out of airplane mode. Some won't even respond to that, and have to be powered on and off. Our speculation in regards to the varying severity is that it more than likely depends on how aggressive the phone's battery conservation software is. If a device loses connection, it may think it's in a "fringe" coverage zone and stop attempting to reconnect to the network to avoid wasting battery. It could also be that the device's software is just poorly written to deal with such regular failed attempts to get network authentication.
Verizon has promised fixes for this issue on almost every 4G LTE phone it has released. Some updates to phones like the ThunderBolt have decreased the prevalence of the problem for some users, but it seems there has been no "magic bullet" as of yet. Verizon has specifically said it's investigating the issue on the Galaxy Nexus, but we wouldn't expect miracles given their track record on this debacle. My DROID Charge review unit had the problem. The ThunderBolt obviously had the problem. My DROID BIONIC has the problem (the new update did not fix it), and now the Galaxy Nexus is suffering from it as well.
Of course, the root problem is Verizon's obviously flawed implementation of its new authentication system, something they've doubtless been working to correct. The fact that devices are so often failing to authenticate is an issue for Verizon to resolve on its end, so let's hope they're nearing a solution.