I e-mailed Verizon support (since it was 2am when I decided to deal with this issue ), and here was his response:
My name is Brad. I will be happy to review your account to determine what further can be done. Considering your past experience, I understand your hesitance to go the warranty replacement route.
Looking at your account, I do see the notes left by the representative. Doing a little research into this issue, I see that you are not the only one impacted by this issue and that it has still occurred with Worry Free Guarantee replacements as well. With Samsung's warranty policy the only thing we can offer is to exchange it at this point with a warranty replacement. Now there are still a couple options.
First, I would contact our Technical Support team at 1-800-922-0204 Option 3. They do have a few more tools at their disposal to try to fix the issue with your phone. Second is that the Jelly Bean update should be released soon to your Nexus that would fix this issue. While not provided with an exact date, it should be soon that the update is rolled out to the Samsung Nexus' on our network. With 3G working and the rest of your phone working fine, you could hold out till the update. Finally, you could contact Samsung itself since the warranty is through them and they require a warranty replacement.
First though, I would contact our Technical Support Team first, and then we can progress from there to resolve this issue for you. Thank you for your patience in this matter. Have a good weekend.
So, seeing that, I went to Samsung's site and talked to one of their representatives who wanted me to mail in my phone, but told me it would take them 2-3 days to receive it, 5-8 to fix it, and 2-3 to receive it back, and with my job I'm just not able to not have a phone that long. I don't have any junkers around even to transfer to while it's gone. So sadly it looks like that isn't a viable option for me at the moment.
Seems like I'm forced to really, REALLY hope he's right about Jellybean fixing whatever the heck is wrong with my phone.