und von mir auch noch ein Tip:
Genau so wie du das beschreibst passiert es mir immer wieder, wenn ich ein neues Handy koppele, allerdings ist das dann weil ich zu langsam war.
Wenn du im Auto auf "koppeln" drückst, läuft die Zeit.
Wenn ich dann erst beim S4 in Richtung Bluetooth Einstellungen gehe, um irgendwann das Connect zu sehen und zu verbinden, laufe ich in ein Timeout. Das Connect kann das Handy nämlich erst sehen, wenn du in den Einstellungen vom Bluetooth bist, vorher ist es unsichtbar.
Ich gehe also dann immer zuerst in die BT-Einstellungen des Handy, dann starte ich im Connect das Koppeln.
Vielleicht ist es ja so einfach...