I didn't see it posted, but here is something else to consider: swapping basebands
**disclaimer** I'm NOT running a CDMA Gnex, I'm running the GSM version
all factory images I've tried have all come with a European baseband. Yes, it worked, but it was slow to grab signal, and would drop 4G often.
Once I unlocked the bootloader one of the first things I tried was swapping basebands to a North American one. For me this made more of a difference then going from 4.0.2 to 4.0.4.
Yes, I realize that CDMA and GSM are different beasts. And yes, Verizon should take some heat for not pushing the update sooner. They should also look into why its hurting SOME people's phones while improving others. Could be apps installed, could be location, could be a bad install, or a host of other problems.
But having said that, its worth a shot, isn't it?