Android - Bluetooth discovery doesn't find any device

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_LOCATION or ACCESS_COARSE_LOCATION permissions

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.

Bit late to the party but this may come in handy for other people.

You need to do two things

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

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

to your AndroidManifest.xml

2. Make sure you're requesting the permission on runtime as well for Android 6.0 Devices by using something like this

   int MY_PERMISSIONS_REQUEST_ACCESS_COARSE_LOCATION = 1; 
   ActivityCompat.requestPermissions(this,
           new String[]{Manifest.permission.ACCESS_COARSE_LOCATION},
           MY_PERMISSIONS_REQUEST_ACCESS_COARSE_LOCATION);
   

   just before mBluetoothAdapter.startDiscovery();

If you don't do step 2 you won't be able to get any Hardware Identifier info on device with Android >= 6.0

UPDATE/EDIT:
Example with Android Version check and alert dialog as warning

if (Build.VERSION.SDK_INT >= Build.VERSION_CODES.M) {  // Only ask for these permissions on runtime when running Android 6.0 or higher
    switch (ContextCompat.checkSelfPermission(getBaseContext(), Manifest.permission.ACCESS_COARSE_LOCATION)) {
        case PackageManager.PERMISSION_DENIED:
            ((TextView) new AlertDialog.Builder(this)
                    .setTitle("Runtime Permissions up ahead")
                    .setMessage(Html.fromHtml("<p>To find nearby bluetooth devices please click \"Allow\" on the runtime permissions popup.</p>" +
                            "<p>For more info see <a href=\"http://developer.android.com/about/versions/marshmallow/android-6.0-changes.html#behavior-hardware-id\">here</a>.</p>"))
                    .setNeutralButton("Okay", new DialogInterface.OnClickListener() {
                        @Override
                        public void onClick(DialogInterface dialog, int which) {
                            if (ContextCompat.checkSelfPermission(getBaseContext(), Manifest.permission.ACCESS_COARSE_LOCATION) != PackageManager.PERMISSION_GRANTED) {
                                ActivityCompat.requestPermissions(DeviceListActivity.this,
                                        new String[]{Manifest.permission.ACCESS_COARSE_LOCATION},
                                        REQUEST_ACCESS_COARSE_LOCATION);
                            }
                        }
                    })
                    .show()
                    .findViewById(android.R.id.message))
                    .setMovementMethod(LinkMovementMethod.getInstance());       // Make the link clickable. Needs to be called after show(), in order to generate hyperlinks
            break;
        case PackageManager.PERMISSION_GRANTED:
            break;
    }
}