Guess why I found this post Juz? I have the exact same problem. I have a 2 year old Toyota Camry with a Toyota factory built-in car kit and since switching to the galaxy s3 nobody can hear my end of phone calls.
I can use the car kit to listen to music from the s3 and can even control the music with pause/stop/previous/next buttons from the carkit, but the problem is the microphone is dead.
The bluetooth connection actually takes the microphone function away from the phone over to the car kit, but then doesn't work... Previously I was using a HTC Desire and had no problems at all with the same setup...
I've tried unpairing the devices several times, but to no avail.
I'm not sure what to do next, but I can't change the car kit as it is a factory one and actually works really well with every other phone except for the galaxy S3.
Any help would be much appreciated.