I've seen some similar issues reported, but they were for specific cars/stereos, and the symptoms were different, so I'm posting about mine:
Phone: Samsung Galaxy SIII, Android 4.3.
Car Stereo: Pioneer AVH-X2500BT
This is a stereo I bought and installed myself. All of its features worked fine, and I was enjoying making calls using voice dialing via the stereo. Then, I installed the 4.3 update to the Galaxy SIII. Ever since (literally, I made a call that day before installing it, and tried shortly after), I cannot use the voice dialing feature. Any attempt to use voice dialing or voice commands via the car stereo will fail. Here's what happens:
I do a long press on the car stereo's Home button to initiate voice dialing. On my phone, S-Voice starts up, and a Toast (little message) pops up briefly that says "Check in-car audio". When I talk, the little animation on the microphone button in S-Voice does not happen, meaning it's not hearing anything. The car stereo shortly cancels out of voice dialing mode, as though it timed out, or something.
I've tried switching to Google voice, but the same thing happens. I've tried all kinds of configuration on both devices. I've unpaired and re-paired. Nothing.
Also, turn-by turn directions from Google Maps appears to not work. The app thinks it's giving them, and when I turn the car off, the voice suddenly works from the phone, but it just won't come out the stereo.
All other features work fine, including Pandora, and streaming Bluetooth audio. I can even make phone calls, by accessing the contacts and recent call list from the car stereo. The calls work and come through the stereo fine. Literally voice dialing and Google Maps are all that doesn't work.
Does anyone know how to fix this?
There could be any number of factors that may be affecting this, byounie. It may be that the firmware on your car stereo headunit may need to be updated. My direct recommendation to check first would be to access your bluetooth submenu, and next to paired info for the Pioneer AVH-X2500BT, you should see a little cog wheel/settings icon. Please select this, and start unselecting everything available there. Work your way up, and enable and test these different settings one by one, to see if there is a conflict between Google Maps and Voice dialing services. Let us know what happens, byounie.
Follow us on twitter @VZWSupport
I just tried that. There were only 2 profiles: Use for Calls, and Use for Music. I tried having first one and then the other on. Neither one worked. Turning off Use for Calls disabled the entire call feature on the stereo. Turning off Use for Music made no difference regarding calls.
This problem didn't occur until I installed the Android 4.3 update to the phone. Did that update include changes to Bluetooth support that might have made it incompatible with some car stereos? It appears a lot of stereos are having problems with this release. I think if we knew what changes were made, it would be easier to track down the problem.
Thanks so much for all you've tried byounie! I've researched and cannot see why this would have changed with the new update. You can try reaching out to Samsung to see if they can further assist with this issue at http://bit.ly/ZG8jl0
Follow us on Twitter @VZWSupport
".. I've researched and cannot see why this would have changed with the new update."
There are numerous posts on 'THIS' site from users complaining about Bluetooth connectivity problems with the 4.3 update on Verizon. There are hundreds more spread all over the internet complaining about this since last December. Where did you do your research, at the Apple store?
I have solved this issue on my own...sort of.
I had tried S-Voice, Google Voice (which crashes), and Dragon (which gives an error). I went' for along time without this feature in both my Galaxy S3, and then my Galaxy Note 3. Same problem.
On a whim, I installed Dragon Mobile again and tried it out, and it worked perfectly right away! Looking back at recent changes, I remembered that I had Disabled S-Voice by disabling it in the System Settings->Application Manager. That solved the problem!
Apparently, S-Voice has a service that connects to the stereo when the phone connects to it. It hogs the connection, even though it won't work with the stereo, and so no other app will connect.
Just stopping the S-Voice app isn't enough. You have to completely disable it, so that its service(s) won't run.
So, S-Voice is bad. But luckily, Dragon is better, so I'm very happy!