Yo también tengo problemas con Android 6 (6.0.1) y el Bluetooth del coche, un Golf con el sistema operativo también actualizado. En mi caso, puedo recibir y hacer llamadas... pero no me detecta la lista de contactos :
Con Android 5 todo iba perfecto...