Same pairing issue with the Cosmo (I'm pretty sure this is more due to the cheap mouse than the Gemini/Cosmo BT as my other BT stuff paired easily) but once paired all is golden. Also the Android on the Cosmo has an optional trusted device feature which holds the Cosmo logged in while the mouse is active. Handy but I'm not sure if this is a good idea from a security perspective.
Hmm, I have paired two BT headsets and my Thinkpad BT keyboard/trackpoint, and they all paired properly on the first try.
The only weird BT behaviour I have experienced so far are these:
1) if I'm on a phone call AND using a BT headset, my WiFi data is iffy*. I have not tried this on 3G yet (data flips from 4G to 3G when on a call, I think this is normal for all phones); and
2) If I'm on a call AND using BT headset, my BT keyboard does not work at the same time. NOTE: BT headset and BT keyboard do work together otherwise, though. I frequently listen to music and mouse/type with BT keyboard simultaneously on my Cosmo.
* Iffy here means that webpages can be slow to load, and when I test further by typing something to my IRC server, sometimes it takes many seconds to echo back while other times it echoes back almost immediately.