I had this while using a Linux machine with a Nexus 4 running Android 5.1
The fix was to enable both ‘debug over USB’ and ‘connect as MTP’. The opposite is true when using the same device and Android Studio and adb on OSX though – to allow Android Studio to recognise the handset, I need to disable ‘connect as MTP’.