Yo doy por "solucionado" el problema. Ayer durante varias veces y largos ratos, estuve escuchando música en el coche y todo funcionó perfectamente.
Siempre, como ya dije, conectando primero el bluetooth del Redmi y después encendiendo el kenwood. En mi anterior huawei era indiferente el orden de conexión. Lógicamente, no debería de ser así. Por lo que he leído, la principal causa de los conflictos con el bluetooth y también el wifi, es la versión Lollipop 5.0.2., incluso en otros terminales.
Otra cosa, y esto es un tema de miui, es que el bluetooth siempre indica 0% consumo, aunque lo tengas todo el día conectado. Es curioso, ya que parece consumir bastante batería.
Espero se solucionen los problemas de los demás compañeros.