After seeing this thread tonight I noticed myself I was having the same problems. I was getting voicemails while on a phone call to my Girlfriend and noticed it never rang through. I then tried myself from my work cell phone and sure enough same problem. My phone is pwned so I was worried it was the problem so I just did a restore and still exists. I called AT&T and for some reason the call waiting, call hold, and something else was turned off!
This is a free service but sure enough it was unchecked and I was unable to check "Call Waiting" from the phone preferences on my iphone settings. Make sure you have this checked if your having these problems and also call AT&T to ensure it is turned on!