For those of you who don't know me (which is probably most of the board here), I had the first car in the U.S. with factory Bluetooth, a 2003 5er Series. I also ran an independent testing project for the BMW CCA to determine compatibility of then-current Bluetooth mobiles against the current BMW Bluetooth system.
I found myself unable to get my BlackBerry Torch to pair with the car despite multiple attempts. Then I looked at the number of devices with which my Torch had been paired - numerous MB Bluetooth entries, a few Land Rovers, a few Jags, a few VWs, an Audi or so - well you get the picture.
I removed the MB PHONE entries and power-cycled the phone.
Voilą. Successful pairing and phonebook transfer.
(I already had the Bluetooth paired to my iPad for streaming music while I was in Germany with the car by the way.)