It sounds to me like you are missing the service book that controls the internet. If you are still having issue go to:

https://bis.na.blackberry.com/html?brand=vzw  It will ask you to create an account including the pin number for you phone (if you never had one before). Once you do this you will find a link under "Help" called send service books. Click on that link and those rights will be sent to your phone. If that doesn't work then there is something wrong on the Verizon side of things.

Hope this helps.