The phone sees "CAR M_MEDIA" and the head unit searches, but it seems like as soon as they see one another, the head unit says it can't pair and then a bit later the phone says there was a pairing error. I am running Android 5.0, but it happened on 4.4.4 also. I took it to the Toyota dealer today and they tried everything I did with the same result--I had hoped and thought they had a Bluetooth stack update, but apparently they thought I was clueless about how pairing works. Anybody else had this issue and have any ideas? I searched here and on the Web and so far haven't seen anyone completely unable to pair. I tried turning Bluetooth off until the head unit starts scanning, tried initializing the head unit before trying to pair, and a number of other fruitless attempts. It seems likely a 2011 head unit wouldn't know how to talk to a newer Bluetooth device, so the only thing I can think of from here is to try JBL to see if there is a Bluetooth stack update for the head unit. The phone pairs fine to other Bluetooth devices.
Tried that just now. First the head unit says "Unable to pair with phone" and shows "Failed" in the display, the phone says "Error: Unable to communicate with device". Just got off the phone with Toyota customer care and they said to have the dealer run a Bluetooth diagnostic. What a pain in the behind. With the car almost 5 years old, I doubt the Bluetooth module is still under warranty and I also doubt it is cheap, especially installed.
Even though the BT pairing fails, does the S5 show up as a device on your phone? If it does, select the device and select Pair or Connect, whichever it is. You may have to do this several times. I had to do this a few times with my S3 to get it to work initially.
I think you mean the head unit? Yes, it stays in the S5 list, but I get the same error when I try to connect to it. I think there is an Android "safe mode", I am going to try that next.
Solved. For anyone else having this issue, the issue was the passkey. It worked when I changed the passkey on the head unit to 0000. From what I saw on an Android forum, changing the passkey to 1234 or 0000 will work. I never got a passkey request from the phone, but it did pair successfully. Apparently on the Gen III non-navigation radio you can't stream A2DP, but I can transfer phonebook entries via Bluetooth one at a time, and of course the phone works.