You can also try to turn off "noise reduction". This solved my problem when I make voice calls, but I had to do it everytime I wanted to make ? call, so in the meantime I have sent back my phone for repair.
You can only turn off noise reduction once the person you are calling has picked up the phone (or when you have picked up the phone when receiving a call). Once this is done you have to press the menu key and there should be an option "noise reduction off" that should appear. I have attached a screenshot that shows the option.
I have read on several forums that not every samsung has this option. I've got an unlocked version myself, so no bloatware or modifications from a carrier (just samsung bloatware ).