I am running CyanogenMatt and have just paired and connected my bluetooth headset.  It is working.  I had the initial problem of paired but not connected.  I shut off my headset, turned it back on and my phone asked if I wanted to connect.  And it did.  It works.  I shut it down, re-powered the headset up again, and it connected automatically.  This rom is looking good.  No problems so far.  I have my PAYG t-mo Sim in for now.  If it stays stable, I will move over my ATT sim!  
 
I wondered if shutting off headset after pairing, then turning it back on would have gotten past the problem of not connecting on the other roms?
No errors so far!