I've experienced this twice now, both times resorting to a hard reset to try and correct the problem. The second time, it didn't work. After doing some searching I found someone complaining about voicemail not downloading into visual voice mail and it reminded me that I saw the same thing on my device.
I went in to phone settings, switched it off, and restarted my phone and everything was fine. I later called my voicemail to find I actually had four messages, none of which had downloaded to my device. It must be getting stuck in some sort of loop trying to sync voicemail.
I couldn't care less about visual voice mail and I'm super happy I figured out what the problem was.