[Galaxy S II Q&A, Help & Troubleshooting] Ryou_Concord:
Alright, well, I've had a lot of trouble in this area as well, and I have found a few ways to get the Bluetooth headset working with Skype. I'll tell you now, that it's probably got more to do with Skype than whatever ROM/kernel you're running. I tried this on my stock 4.2.2 Nexus 4, and on CM10.1 stable, running Franco's Kernel r151. The headset I'm using is the LG HBS730, which has served me well in all tasks on my phone other than Skype, of course. This is a long-standing problem I've had with Skype; the conspiracy theorist inside of me wants to believe it's because Microsoft wants to push their Windows phones by purposefully making their Android client suck, but the realist in me hopes that's not true (what with the wide range of Android hardware that the Skype Client would have to support). And besides, Skype's as broken on Windows phones as it is on Android, minus the glaring battery issues.

Okay, to get the headset working, I've done the following.

1. Before I start skype, I turn my bluetooth headset off. I wait until it disconnects.

2. I turn my phone's Bluetooth off and on again. Do not reconnnect the headset yet.

3. Sign into Skype (I'm using the version that was updated on July 10, 2013, since I can't seem to get a real number on the version of this miserable app).

4. Join the call that your friend(s) are in. You will start to hear them over your phone's loudspeaker.

5. Turn your Bluetooth headset on, wait for it to connect. When it connects, Skype should automatically recognize it, and start using both the mic and the earphones on the headset, and you should be able to talk normally.

Here are some things that will annoy you, though:

When you get a regular phone call, the Skype call will be put on hold. When you end the phone call and try to rejoin the Skype call, Skype will still see the headset as connected, but will continue to use the phone's speaker and microphone.

This is going to happen a lot, and here's how to fix that:

1. Leave the call, and sign out.

2. Close the app from the little task manager thingy (If it's a Galaxy SII, just hold the home button and swipe it away).

3. Disconnect the Bluetooth headset. You can turn your bluetooth on your phone on and off again real quick if you think that helps--I have yet to determine if it does.

4. Sign back into Skype, and join the call.

5. Turn your headset back on again, and Skype should connect to the headset.

For some bizarre reason, I have not been able to connect my headset to my phone, and sign into Skype with the expectation that anything will work, at all. I wish it weren't so complicated, but it is.

Oh, and FYI, don't bother with Skype premium. Group video doesn't work on Android phones OR Windows phones (even from Windows desktop to Windows phone, my friend and I tested; way to sell broken services, Microsoft!), so if you're on-the-go a lot, it's a total waste of money. Also, if you're bike riding, you're probably just going to piss off your friends in the Skype call with all the ambient noise. The mute feature on my headset is not recognized by Skype, so I have to dig my phone out of my pocket to mute it from the screen.

I hope this helps, but more than that, I hope that one day, Microsoft will restore my faith in Skype. But considering it took them this long to revise their app to the point where Bluetooth even pretends to work, I'm not crossing my fingers.