Just called Apple and they confirmed this is a know issue. I have this problem with my 5S on the T-mobile network. Anyone else?
This always happens. Call 611, voicemail help, reset password. It'll work then. You don't need the reset password...just the refresh.
Had the same issue with Verizon. Call your cell phone and leave a message. It should clear it up. Worked for me.
This happened with my Dad's phone. He reset the password, called and left a voicemail and then restarted the phone. At first it didn't seem to help but then after about an hour he got a voicemail notification and everything was fine again.