Prueba:
-Baja la barra de notificaciones para activar el bluetooth.
(Si se te pone en verde es que esta activado, pero OJO! esta oculto por defecto)
-Menu > Ajustes > Conexiones inalámbricas > Ajustes de bluetooth
Marca la casilla VISIBLE.
Durante 120 seg tu bluetooth será visible.
Prueba buscar ahora desde el coche a ver si ves tu telefono entre los dispositivos encontrados....
Suerte