I don't think that it has anything specifically to do with being Jailbroken. Mine has been working fine so far since I cleared the messages in both the at&t system and on the iPhone itself. I have been Jailbroken since it was first possible, and Voicemails were working fine as of about 2 weeks ago (the last message in the list was from August 7th). The oldest new message that wasn't delivered to the iPhone on the at&t system was only a few days old, so I'm not sure at what point it actually "broke"...
History of what I tried:
I had previously reset network settings, but not reset all settings. Maybe that would have cleared the voicemails and fixed it as well? I also tried resetting th password both via the iPhone Settings.app as well as through 611's automated system. However, through the automated system, it changed it to a temp password that was SMS'd to me, and on the iPhone when going into Voicemail tab, it asked me to set it up as if it were a new Voicemail account, never asking for the temp password but instead having me create a new password and set up the greeting. A bit odd, but afterwards it still didn't work until I cleared the old messages off the iPhone.