I'm using Handcent btw. I tried a fix that must work for some but it didn't work for me. Maybe you guys will have more luck than I did. Back to searching......
I can't take credit for this. I just copied and pasted it from XDA's forum:
1) uninstall Go SMS Pro (or other SMS program you are using other than stock)
2) Go to the Voicemail .apk via Settings > Applications > Manage Applications > Select the All tab > scroll to Voicemail
3) Force stop & Clear Data for the Voicemail .apk
4) Go and update your Profile (settings > about phone > system updates > update profile
5) Open the Voicemail app and it should update provisional status.
6) Let it sit for a minute and pending messages may download on their own.
7) Call your phone and send a test voice message.
8) re-install Go Sms Pro from the Market, but in the setup where it asks if you want to disable all other sms related apps, don't check that (this is the specific problem).
9) go into the stock SMS program and disable notifications from within it, if you don't want dual notifications.