Talked to Verizon rep again today:
He said they've actually been working with LG (the manufacturer)on this, so obviously it's being reported by a decent amount of users.
Had me download an app in the App Store called 'Restore Connectivity', the one with the LG logo. That app mentions something about 'Easy Battery Saver+Task Killer' having a problem on the LG phones and instructs you to uninstall it first. I didn't have that app loaded, but had JuiceDefender, so I uninstalled it and then ran the app. I'm skeptical if it did anything because when you run it, it goes through and eventually has a Restart button. If I press Restart the app force closes.

So, who knows. It certainly didn't fix the issue.
Went to a 2nd tier rep at that point and she had me try launching in Safe Mode (power cycle, hold power til LG logo comes up, when LG logo flashes, hold menu button until the OS boots and you see 'Safe Mode' at the bottom. This was to rule out a software issue. Problem still occurred when I use the Browser to just look at websites. Still dropped in and out.
Also had me check Global data roaming, it was unchecked.
After all that, she suggested that she send me a new phone free of charge. I told her I was sort of afraid of having the same issue, but she said that they don't receive many calls on the Lucid per week (And took a swipe at the Galaxy Nexus

, apparently that one must be a nightmare to support).
So, we'll see what happens. In any event, it looks like it is a big enough issue that LG is involved. I *did* take the opportunity to ask the first rep if there was an update coming down the pipe - but he didn't have any info and said he wouldn't be surprised to see an update to ICS. He mentioned Q1.

But honestly, he sounded like he was just purely speculating.