you need to manually download and install the verizon prl...
http://corolada.com/prl/verizon/50855.prl
-Download that file, and copy it over to your phone.
-Go to the phone and type ##775# (##PRL#).
-Enter your MSL Number (6 digit unlock code, verizon is all 0's)
-Follow prompts
-Browse to where you extracted the update file, select it, done!
Once that is done, I'd still do one over the air, using *228 or *22899 to ensure you have the latest/proper one for your plan, but that one should atleast get you to verizon.