I've had similar problems with Samsung phones on bluetooth devices. Not on the BMW specifically but on an aftermarket Kenwood head unit. All my other phones worked fine but the Samsung just wouldn't work. Seems like whatever they are using for their bluetooth software doesn't play well with others.
09 E90 M3 - Interlagos Blue / Black Novillo / Sycamore Anthracite / Eibach / HRE