Почему приложение не находит bluetooth устройства?

Проблема такая: есть приложение, которое выполняет поиск bluetooth устройств и подключается к ним. На Android 5 всё отлично, но начиная с Android 6 приложение просто не видит ни одного устройства (хотя сам телефон их находит).
При этом я добавил в соответствии с новым API:

<uses-permission android:name="android.permission.ACCESS_COARSE_LOCATION"/>

У кого такая проблема была? Как решили?