Did you try changing to a different Codec, or making one the "preferred" codec and allowing an alternate? I'm not way up on my codecs right now so this might be backwards, but I believe I have mine set to prefer 711, which I think it the best one, but to support 729 also. I like to use the best codec in a wired desktop environment, but if you are using a device on wireless and you are set for 711 only, for example, there may be a bandwidth issue that is affecting the call quality and you might want to let it downshift to a lower codec.
Playing with the codec settings would be my first step. From there I would need to have the actual problem and trial and error to see what works.