Has anyone found a fix for this yet? I have a Samsung Intercept and the same problem with not being able to connect. It pairs with my car, but does not connect. Sometimes, after I do a factory reset of the phone, it will connect, but only just that one time and never again until it's reset. Highly inconvenient.
I'm pretty sure it's the phone and not the car, because my old Nokia connected just fine every time without me doing anything. All I had to do was turn the car on and it would connect.