I work at a retail store where these are sold and I know that Samsung phones before Galaxy S7 have a bluetooth bug where known devices are unable to connect. The solution is to go into settings>Apps/programs>all and find the bluetooth android service. Force stop the bluetooth service and reboot the phone. This should fix the connectivity problem.
