I just got the HTC Amaze and I can't seem to pair either. My phone can't find the BMW, but can find other Bluetooth cars/devices in the parking lot. I paired my HTC Touch Pro with no problem over a year ago. I wonder if this has anything to do with the new Android OS or Bluetooth version.