Take the phone and drop it in a lake, then get a new phone (not iphone) and all will be fixed.
Or you can except the fact that apple is not what it used to be, because I have the same problems.
I'm in a contract, but when it ends, I will switch to another brand.
Visual voicemail should be working, no excuse for this.
I wish I could be of more help, but the apple store could not help me, at&t gave me the same brush off, and all my tech friends at work are baffled about this problem.
I wished I had waited for the reviews, before downloading the ios 7.
Unfortunately, I did ask at&t about this problem, and then apple, and then went online to find so many others with the same problem, most of them with Verizon, T-Mobile.
I have 3 iphones, 2 5's and one 4.
This problem never existed before the ios 7 was downloaded.
So do the math. The phones worked fine, then a 4 hour download from apple, and boom, no visual voicemail.
Today I took this phone to a cell phone store, and even this tech, who has helped me before could not explain this problem.
So whats up with the ios 7??