I've had pairing problems too (I have a Samsung SGH-T519), but once I 'authorized' the car on my phone's BT menu (I have a Jabra earpiece too) it connects automatically everytime. I now have a different problem though.

When I place calls from the handset, it works fine. However, when I place calls using the voice-activation, the systems kills the call as soon as it starts dialing the selected number. I went to the dealership where I bought the car and they suggested pairing the phone again (which means I have to delete the phone which deletes my phonebook). Off course I'd like to prevent deleting my phonebook and having to (pain in the you-know-what) re-enter it. Any suggestions?