For a while I have been using a Nokia BH-604 bluetooth headphone ans everything was working fine when after I pressed a button on the headphone I lost all sound. In my attempt to fix this is tried different settings and during this I set the Mode of the device (in Settings -> Sound) to Off. The headphone disappeared from the list with sound devices and I can't get it back there.

I deleted the bluetooth pairing and paired the headphone with the computer again, but that didn't help. The issue is not with the headphone, because on my iPad the headphone is working perfectly.

Does anyone have an idea how to make my headphone come back in the list of audio devices? I am using Ubuntu 12.04