Ich weiß nicht genau, ob wir da den gleichen Effekt haben... bei mir ist es ein S4 mit CM-Betriebssystem... auch hier gibt es ein Problem, da scheint es wohl eine bekannte Schwäche zu geben.
Bei mir ist es die Telefonhistorie, "Call-Log", d.h. die Einträge der Historie, wer angerufen hat, wer angerufen wurde, usw.
Wenn ich die komplett lösche, dann geht alles gut. Ist die aber voll, dann stürzt das Bluetooth im Handy beim Verbinden ab. Anscheinend wird zu Beginn genau diese Log übertragen, und da klappt irgendwas nicht.
Mit dem Telefonbuch selber hat das aber nix zu tun, das wird nur einmal beim koppeln, oder auf Anforderung im Menü von dir selbst, übertragen.