He might try getting a replacement SIM - that's caused this kind of issue for other users. But first try the Kies desktop software.
Kies won't update firmware for the Verizon version. It just says it can't do anything for firmware with this model.
First, get the SIM replaced and see if that helps.
Second, factory reset and see if it can find the update then.
After that, you have 4 choices:
1) Be patient, but accept the fact that you may never see an update. The original JB update has been out for some time and your device should have taken it by now.
2) Get Verizon to update it or replace it. (yeah, right...)
3) Use ODIN to flash the full JB ROM. (If a factory reset doesn't work and you want to stay stock, this is what I'd advise.)
4) Root and flash a different ROM and be off the standard OS path.