Check to be sure your Mobile network is Verizon Wireless (Manage Connections...Mobile Network). Then look at your Mobile Network Options, Data services should be ON, Network selection mode=Automatic, network Technology 1XEV.
You can also call Verizon customer service (800-922-0204 or *611 from the BlackBerry) and have them check the messaging set up to be sure it is provisioned properly.
Also take a look at your firewall. It normally doesn't stop outbound sms messages but will definitely keep incoming ones out. I've experienced this several times messing around with the firewall settings. If that's not the problem a hard reset might do the trick. As SuzyQ said, you might be experiencing some provisional issues or SMS & MMS may be blocked by the primary account holder if it is someone other than yourself.