First make sure the icon isn't hidden. On the homescreen where all the icons are, click the menu key to the left of the trackball and click Show All.

If you don't find it, then do a 30 second battery pull with the phone powered on and resend service books.
If none of that works, I'd call Verizon support.