I have been having the same issue and another forum I found said this:

It appears you're only having an issue with voicemail and not your text messages or other services so it's likely that we just need to reset the mailbox. To do so, please go into Settings>General>Reset>Reset the Network Settings. Your greeting and existing voicemail messages will be unaffected during this process. Once completed, have someone leave you a voicemail to ensure it notifies you right away.

It worked for me.