That's frustrating. I'm able to develop little apps with Xamarin and debug them directly on my old phone, an HTC One S with Android 4.1 (Jelly Bean).
I recently got a HTC One M9 and updated it to Android 5.1 (Lollipop). And I can't see the device on the Xamarin devices list.
My pc can see the device. The debug\developer option on the device is active. The Xamarin version is 5.9.4 (build 5). Any idea what I'm missing?