However, I accidentally discovered a trick that seems to improve the connection. Once your phone is recognized, use Siri. Basically just start Siri up and ask her anything. After an initial connection through Siri, it seems that the phone is paired and will dial out normally.
Yup--I've been doing this for years. It is great for voice dialing, and for reading and responding to texts, as long as you can reach the Home button on your phone while driving. "Call Mom" "Which number, home or mobile?" "Home" "Ok, calling mom".