Ich habe weder mit der original Samsung Android Version (4.03) als auch mit der jetzigen modifizierten Android CyanogenMod 10.1 (JellyBean) Version keine Probleme, wichtig ist aber, wie schon beschrieben: Lösche insbesondere im Radio alle bisherigen Bluetooth Verbindungen, auch, falls vorhanden aus Testverbindeungen zum Radio, die in Deinem Smartphone. Bei mir hat es nach dieser Aktion sofort geklappt, musste aber vorab die Firmware meines Autoradios (Kenwood) updaten, da dieses nicht alle Dienste des Bluetooth Protokolls unterstütz hat, letzteres sollte aber bei Dir nicht notwendig sein.