I have been seeing/reading that starting with Android 6.0.0/Marshmallow some users are having BT connection problems.

I hear that some improvements with some models may have been made with Android 6.0.1, however, there are still some problems even with 6.0.1.

So for anyone having BT connection problems, please note what device you are using and what version Android OS you are running.