I've used my Bluetooth headphones with my Samsung Focus for a long time. For some reason, recently, I can pair to my headphones, but when I press the button on them to pause/unpause, the audio comes out of the phone speakers, not the headphones.
The controls work, but the audio doesn't come out, so I think it's paired, just not correctly.
I've tried deleting the device and re-adding it, but it doesn't seem to work.
What I did:
Turn off Bluetooth on the phone. Delete the headphones from the device list.
Attach the headset to the USB cable as if you were charging it for 3 seconds. Then disconnect it. Repeat that 2 more times. (I did it a bunch.)
Now the audio is coming through loud and clear.