Sounds like a setting issue on Verizon's end. I experienced a similar problem and Telus just had to double-check my account settings. It turned out that when I got my replacement Storm initially, the switch didn't go through correctly. So, flip of a switch and I was back up and running. Have you had them check to ensure that your new Storm is properly set up on the data plan? They may have the voice plan set up correctly, but the data plan is on a previous Storm.
I don't know if this is the case, but it may provide another suggestion.
Krypto on CrackBerry Forums, BB Support Community Forums and Future Shop Community Forums