[brightedge]

Try this:

Start > Settings > Phone > Services
Select "Voicemail" from the list, then hit "Get Settings"
Select "Clear"

That should clear the count.