IMPORTANT EDIT: Since this solution no longer applies to current Android versions, consider Replacing the ULF/Bluetooth Module or see this thread which has pre-built Google-Pixel binaries.
Background: With Android 4.2 Google introduced a new Bluetooth stack which broke bluetooth connections with some older car kits (see the comment in https://code.google.com/p/android/is...etail?id=41625 ... it is for the BMW E46 , but this also affects other BMW series with the same old Bluetooth ULF, like E39, older X3, X5 (E83) and Z4 and probably also some Audi and VW). The problem this addresses, is a bluetooth disconnect within 5 seconds after pairing.
I'm the original submitter of that patch to Google AOSP which was ignored by Google but subsequently included into CyanogenMod (https://android-review.googlesource.com/#/c/48164/ ) and with purchasing a new new phone (a Moto X 2 2014 with Lollipop) I had to revisit the issue (my car is still the same BMW E46).
This binary patch applies to the Moto X 2 (2014) Lollipop 5.0 bluetooth library, but probably the same will work for Android 4.2.2, 4.3, 4.4 and other phones too (the bluetooth C source code in that location is still unchanged since android v4.2, see the posts linked in step 4 below)
Essentially I found that it is possible to patch the bluetooth lib on the phone directly without a complete android build environment (I had tried a full rebuild too, but was unable to get my self-compiled bluetooth library in the Moto X ... if you have a Nexus phone or if you can compile Android yourself, using the source patch is probably easier)
Here are the steps (I'm keeping them somewhat vague to deter noobs from trying to tinker with the files):
To make Android work with those older BMW car kits, it is necessary to modify a behavior of bluetooth in some minor way. This obviously requires a rooted device.
The file in question is /system/lib/hw/bluetooth.default.so
Step 1 (make a backup):
run adb shell and copy /system/lib/hw/bluetooth.default.so to /sdcard/bluetooth.default.so.orig
A backup of the whole system (TWRP or similar) will be a good idea too.
Step 2 (disable bluetooth and download the file to patch to your computer):
On the phone go to settings and turn bluetooth off
Issue: adb pull /system/lib/hw/bluetooth.default.so bluetooth.default.so
Step 3 (generate a hex version of the file, linux):
xxd bluetooth.default.so >bds.txt
Step 4 (edit the hex version):
Find the byte sequence b8ed a8b1 b4f8 6032 93b9 b0f8 08e0 0de0 (it should be around offset 00a1000)
Change it to b8ed a8b1 b4f8 6032 93b9 4ff0 000e 0de0
(edit: in a post below, a user reports a slightly different byte series for a Samsung S4, so if you can't find the above sequence, try ignoring the initial b8ed and start your searching with a8b1 ... or follow suit with another post about earlier Android versions or a post about a LG G3).
Step 5 (create a binary version of the patched file):
xxd -reverse bds.txt > bluetooth.default.so.patched
Step 6 (upload patched binary to phone):
Issue adb push bluetooth.default.so.patched /sdcard/
Remount the /system partition as rw
Use adb shell, then su and cp /sdcard/bluetooth.default.so.patched /system/lib/hw/bluetooth.default.so
Then (still in the shell as su): chmod 644 /system/lib/hw/bluetooth.default.so
Verify that only those four bytes changed: cmp -l /system/lib/hw/bluetooth.default.so.orig /system/lib/hw/bluetooth.default.so
Verify permisssions (ls -l /system/lib/hw and check if the new file has same flags as the rest (rw--r---r---)).
Step 7 (enable bluetooth again):
on the phone set Settings > Bluetooth : on
Make sure it stays on (and doesn't give an error, otherwise make sure the file has correct permissions and/or copy the original file back from bluetooth.default.so.orig)
Step 8 (check with car):
Take phone to the car, pair the device to the car-kit.
It should stay paired and making calls and access to the phone address register should work.
EDIT: In a later post a user says there is also a file named /etc/bluetooth/auto_pair_devlist.conf which has a number of devices blacklisted and to make it work, some entries need to cleaned (commented out or deleted).