For everyone having Blue tooth issues. Below is the fix. Please follow this step by step and it will be solved. I have already taken my mercedes Benz to the dealer and done the software update but that was not the issue. The real issue is with the new phone (Not Ios 8) hardware and how it is working with icloud. The klutz at apple have no idea what they have created and the problems it is causing users. They dont care and the apple tech support is equally clueless. They are happy to sell you a phone and then it is your problem to deal with and they blamed the car manufacturer!! They are not even owning up to this issue and releasing a fix.
BELOW will work ....dont waste time doing anything else
1) Log out of icloud on the iphone – SETTINGS, ICLOUD, SIGN OUT (AT BOTTOM)
2) Delete car/headset from iphone – SETTINGS, BLUETOOTH, SELECT DEVICE, FORGET THIS DEVICE
3) Reset network connections – SETTINGS, GENERAL, RESET, RESET NETWORK SETTINGS
4) Delete iphone from car memory
5) Restart phone
6) Pair to car/headset as normal
7) Log back into icloud to use icloud features