While I suspect the issue lies with the vehicle and not the phone, it occurs to me that others may have had a similar problem and perhaps someone has found a solution - so here goes.
Recently got a 2009 BMW X5 with iDrive and NAV, and while the Droid paired easily, it will not upload the phone book. This is a major inconvinience, because now I have to make all outgoing calls via the phone instead of iDrive or voice commands.
I also have a 2007 3 Series with iDrive and NAV, and it works fine in that car (full phone book, etc.).
Any BMW owners here that have had this problem and found a solution?