Not a phone issue. Apparently Visual Voice Mail leaves the messages on the server. So unless you deleted them, they would all still be in your inbox when you switched phones.
It is most likely a VVM issue. It seems to be spotty and whether it updates the read status. I have noticed on occassion it has not updated that I had listened to a message. So, you are probably getting the message just fine - but the status may not be updating.
Ive been using Visual Voice Mail and haven't noticed any bugs or issues so far. I've had the Storm since 7am on Nov. 21, so it's been nearly a month now.
I had a similar issue when I first got my Storm. I did not setup Visual Voicemail for a few days and was not receiving any notifications that there were messages in my inbox. After activating the VVM all of the messages were there and everything is working properly.
I had a problem like this on past phones. Either there was no voice mail indicator or there was a voice mail indicator that never went away after I deleted the Voice mail. It's not specific to the Blackberry, it's actually specific if you switch devices and they do not provision all of the features from your old phone to the new one correctly, in other words the VM server is sending the indicator to your old phone rather the new one. Once they "reinitialize" it, all is well.
this is a known issue with VVM. Happens to me and hundreds of others. A fix requires vzw to remove vvm mailbox on their end, rebuild it, and then it works. I have had mine rebuilt twice. VVM is becoming a real pain. When it works I love it, but one more time and it's history.