Also, I'm on a 3G on AT&T, and I have had BOTH of the problems I described above;
1) On my old 3G, when I upgraded and jailbroke to OS 3.0, I lost my VVM and had to re-enter some APN settings.
2) On the 3G, when I jailbroke using purplera1n RC2, I had to leave myself a voicemail so that VVM would prompt me to re-enter my voicemail password.
Also, purplera1n is an EXQUISITE piece of software. I will recommend that over redsn0w ANY DAY to anyone who will listen. It's EASIER, FASTER, CLEANER, and functions perfectly with no problems. BUT, it only works on 3G and you said this problem was with your 3G. So you're stuck with redsn0w, which I have limited experience with, though I did use it to jailbreak my 3G.