Es muy raro, pero por las explicaciones que das, me temo que ya has probado de todo y, además, no pareces desconocer el tema. Yo, si estuviera en tu lugar, haría las siguientes pruebas:
1º Reinicar teléfono e Infotaiment (pulsando el botón de apagado durante unos 10 segundos).
2º Si el punto anterior no lo resuelve, probaría con otro teléfono, para focalizar el problema, bien en el coche, bien en el teléfono.
3º Si el problema lo tienes en el teléfono (con otro móvil sí funciona), probaría a ver el tema de la seguridad de tu teléfono, quizás te esté bloqueando la conexión (darle permiso, añadir como dispositivo de confianza....etc).
si has probado todo eso y no funciona.....no sabría que más decirte, nadie ha posteado un problema similar al que describes, en este caso, siempre que hablemos del teléfono, te sugiero exponer el problema en foros dedicados, tales como HTCMania.