I've been having this same issue for over a week now. After much back-and-forth with Virgin Mobile's clueless email, facebook and phone support staff, I finally just talked to somebody in their "Advanced Technical Support" team who seemed to know what he was talking about.
According to him, the issue is that since purchasing Virgin Mobile last year, Sprint is now gradually porting all of the existing VM accounts into Sprint's account management system. Apparently, while your account is "in flight" (his phrase) from the old Virgin Mobile "Siebel" system to Sprint's "i-Care" system 3G and voicemail features will not work properly. He claimed that the transfer process starts right after a payment, and usually takes 7-10 business days, but he had occasionally seen it take up to 15.
I'm still pretty irritated with Virgin Mobile for never communicating any of this information, but at least this guy seemed to be familiar with the problem. I'm going to wait and see if his prediction is correct that the issue resolves itself in a few days when the account transfer completes.