Easy fix, same thing happened to me. My droid would show that I had a new voicemail - I would check it and I would have no new messages. I had some saved messages in there but even after I tried deleting everything, the new voicemail icon would still show.
Finally called Verizon Wireless and they helped me get rid of it.
Call your voicemail. You will hear the message "You have no new messages." If it says anything about you having SKIPPED messages, then you will want to delete those first. Anyway, you will hear "You have no new messages" upon checking your voicemail, then you will want to press option 4. Then you will press option 1 to turn off "Message Waiting Indicator" (don't hang up yet)... wait a few seconds and then press option 1 again to turn on "Message Waiting Indicator". You can hang up after this. This more or less confuses the phone and resets the messages.. your phone must have gotten stuck.
Hope this helps ^_^ !!
p.s. google voice users - no need to get rid of GV or uninstall, I think it's just a glitch with verizon voicemail.. :motdroidvert: