I've actually had no issues and I use bluetooth with multiple devices daily. I've disconnected, reconnected, unpaired, paired, etc and cannot reproduce this. So you guys know, I have not touched the bluetooth stack at all. So whatever the problem is will exist on completely unmodified devices.
Maybe there is a problem connecting to certain devices? Can you guys list out what you're trying to connect to?