A mi me pasa lo mismo, además de que tuve que emparejarlo como dicen con el programilla ese.
No he conseguido solucionarlo. Tengo el BT siempre activado, y me lo coge siempre salvo cuando cargo el movil. Al encender el movil tarda más tiempo que cuando lo enciendes normalmente (supongo que al cargar, hará un apagado más completo) y es entonces cuando enlaza "a medias" con el coche, me aparece pero sin cobertura. Le doy un "toque" al movil para desbloquearlo con el botón de encendido y listos, otra vez enlazado bien..... Hasta la siguiente carga que le haga al movil.