I do not have problems with this device and my in-car bluetooth, surprisingly. I say "surprisingly" because my car seems to be a bit temperamental in the same way that you describe in your post, with multiple phones. Had issues with the SGSII, the Surround on 7720 and on ansar's 8107 build, as well as previous phones.
Remarkably, the Nokia has auto connected every time so far.
But are you talking about streaming audio over BT, or just the voice services?
SLVR-->OG iPhone-->iPhone 3g-->iPhone 3GS-->HTC Fuze-->N1-->BB 9000-->Craptivate-->SGSII I777-->Surround-->iP4S-->Lumia 900-->SGH-I747-->SGH-I317 / iP5-->Lumia 920
Some others I can't remember as well.