If you're on Verizon, dial *86. This will call Voicemail. Even if they say you have no voicemails, it'll cause the visual voicemail to resync and should resolve. We've had this issue on dozens of iPhones with Verizon, and this has resolved for every one.