What version of Android are you running this on? If it is Android 6.x, I believe you need to add the ACCESS_FINE_LOCATION permission to your manifest. For example:
<uses-permission android:name="android.permission.ACCESS_FINE_LOCATION"/>
I had a similar issue and this fixed it for me.
UPDATE: Adding documentation direct from Google on this:
To access the hardware identifiers of nearby external devices via Bluetooth and Wi-Fi scans, your app must now have the
ACCESS_FINE_LOCATIONorACCESS_COARSE_LOCATIONpermissions
UPDATE 2020: We recently updated our application to target SDK Version 29. In doing this, our application stopped being able to discover Bluetooth devices again. We have been using ACCESS_COARSE_LOCATION since this answer was originally written. Changing to ACCESS_FINE_LOCATION appears to fix the issue. I now recommend developers try ACCESS_FINE_LOCATION if targeting 29+. Answer updated to reflect this.