This method may work, go to Settings > Apps > Phone and select Clear Cache and Clear Data if available, this will fix your problem with your voicemail notifications on Android.