I'm having similar issues--came from AT&T with a Motorola Atrix 2, which was great. Now my calls all sound choppy even with full bars. It was so bad I got a warranty replacement, but this one isn't much better. I generally only make calls from a couple locations (home and office), but with full bars, I'd think calls should sound good...?
Did the audio effects setting fix this for you? I tried it with little to no effect.
I'm hoping the JB update (which lists improvements for voice) helps.
UPDATE: I unchecked the Voice Privacy option, which helped. Still not perfect, but better than before.