Take the phone back to the Verizon store and let the people there know that it sucks and that they should complain to corporate about it. Then see what other alternatives they have. Lastly, if that's not going to get a proper phone, just buy an iPhone online through the Apple Store for the Verizon network.

Android is likely to always have these problems, even with Google tightening down, I don't think they'll be able to fix all the cruft these second-tier manufacturers are dumping on there.

I can sympathize with the extra work and headaches you're having to go through here to support this customer. Ouch.