Nexus 6 bluetooth issues

[AC Question]

I am at my wit's end with this nonesense, so any help would be greatly appreciated... I have a brand new Nexus 6 that I had no problem connecting to my car's (subaru) hands free system straight out of the box. Fast forward a couple of weeks and I try to connect it to my wife's car system (also subaru). However, this time around the pairing process fails over and over again. Thinking that there might be some name resolution issues since both cars are the same make, I deleted my car's bluetooth profile on the phone and tried again. This time, I cannot connect to either car.

This is what I have tried:
1. Turned bluetooth off and on
2. Deleted the "Bluetooth Share App" cache and rebooted
3. Erased the systems cache partition
4. Factory reset the phone

1 through 3 did nothing, the last step brings me back to the original problem: can connect to one car but not to the other and if the bluetooth profile is deleted, cannot connect to either car.

Is there anything else I can do short of returning the phone?

 

[B. Diddy]

Welcome to Android Central! After pairing with your car, go to Settings>Bluetooth and tap the gear next to your car. Now change its name to something unique, like "Vader's Wheelz."

Next, try pairing your phone to your wife's car, but make sure your car isn't nearby (just in case the Bluetooth radio on your car is still active). Does it pair now?