I suspect the issue may be beyond just voicemail. I had the same issue with voicemail playback, but beyond that I had some custom ringtones, which stopped working (and I didn't know it), so I kept missing calls even though I turned the volume of the ringtones up. I had also noticed I couldn't record video. I would say "normal" as opposed to the short, MMS smaller file mode, and as soon as I pushed record on the video, it would say "recording failed." I found this forum post
Epic 4g - Music/Videos/Ringtones and Taking Pictures/Videos Unavailable - Android Forums which indicated the Twitter mobile for Android app to be the issue. I just uninstalled that and then unmounted and remounted the SD Card (from the settings menu or you could just pull the battery and reboot your phone to do the same) and then everything is working at the moment. It looks like others have indicated no problems since, so hopefully mine is resolved too. I suspect it is.
Marianne