Buenas almanu,
Mira a mi tu me pasaba lo mismo hace tiempo, con un Parrot y un Nokia N80. Lo asociaba pero al parar el contacto en el móvil aparecía en la lista de dispositivos pero no se volvían a asociar. Total que al final acabé actualizando la firmware del móvil, desmonté el manos libres y lo mandé a Parrot para que le cargaran otra versión de software y no se si por una cosa o por otra pero dejé de tener el problema.
Digo yo, para probar si es el móvil o el coche siempre puedes probar con el manos libres de otro amigo...