Hola,
Empieza con lo más facil, al intentar el pairing tu telefono llega a ver el BT del coche?, si es asi y luego no establece el pairing intenta desactivar la sincronización de la agenda, algunos teléfonos no pueden emparejar porque no pueden sincronizar la agenda del movil, pruebalo y nos cuentas y vamos viendo más pruebas, prueba con otro móvil si puedes con un iphone.
Saludos.