N4 + Sennheiser headphones

I tried to pair my Nexus 4 with a pair of Sennheiser mm 550 headphones. The thing is, the Nexus finds every device close, even the phone of my neighbour, but the Sennheiser right next to it. Is there a special trick to pair it, or does those two devices fit together?

:( seems no one else encountered the same issue by pairing those two devices. I ask the question differently, which wireless headphones mit noise cancellation work with the Nexus 4?