Hi,
for all those of you having trouble with the calling/called party not being able to understand you when using your iPhone 5 via car bluetooth while YOU can actually hear the other party quite well, this might be the reason:
The iPhone 5 is able to use a quite new audio codec called HD VOICE for phone calls which is used in supporting provider networks (e.g. here in Germany, T-Mobile IS actually supporting HD Voice). Obviously, due to the required higher bandwidth, this seems to conflict with Bluetooth. In combination with the new echo cancellation system which was invented quite poorly with the iPhone 5, this leads to your voice being severely garbled, making it almost impossible for the calling/called party to understand you.
I have yet to do some testing myself, but try to switch off mobile data completely or at least 3G before getting into your car. This forces your provider network to fall back to the older audio codec (2G, non-HD Voice), et voilà - the other side should now be able to understand you again. I just tried this method and it seems to work - while not being a too elegant workaround, I have to admit...
I have heard elsewhere that this whole problem is completely fixed with the upcoming iOS 7 - so another possibility would be to simply wait another three days until iOS 7 comes out ;-))
Best,
Gero