I have four sets of BT headphones and all work great with the N7 and newest JB software. Sorry you are having problems and don't know what to tell you my only thought is set them up as I set up all my headphones use Headset Button controller. I do realize this does not help you get them paired and just don't know what to tell you about that except I really don't think your pairing problem is NOT a N7 problem. All mine paired with no problem.
I had the same problem and just figured it out. Turn your PX5s on; turn the Bluetooth off; then hold the Bluetooth button until the blue light turns red(which will put the PX5s into pairing mode); then search for devices on your Nexus 7.
My headset pairs with 3 laptops, two phones and my desktop computer that has a generic bluetooth single but it won't with my n7 and you say its not the n7? Your dreaming.
PS my Bluetooth keyboard and mouse work fine with it.
Mine works with my moto bt headset but has sporadic sound dropouts making movie viewing impossible. Customer service says there is a software prob they are aware of. So i use regular wired for the time being.