VM voicemail notification icon


Ever since buying the S3 from radioshack last week, I noticed that when I power on my device (from the powered down state, not just locked) the 'new voicemail' icon notification icon will be present whether i have a new vm or not. I'll tap the notification and the nice lady will say, "Hey no new messages!" or whatever and the icon will stay. The only way I've found to remove it is to long press the notification and access the App Info. I'll then have to "Clear Data" to get it removed.

This is kinda annoying. I'm not 100% sure what all data this is clearing from the phone app. My contacts/recent calls stuff is still there. Any ideas on what all it is clearing? Any ideas on getting this notification to NOT pop up everytime I turn on the phone? As always, thanks for your help!