Similar to Flavio's answer (https://stackoverflow.com/a/18542792/1064996), it was something to do with the files in ~/.android
(on the host machine, not the phone).
I didn't have ~/.android/adbkey
, but I did have ~/.android/debug.keystore
and my whole ~/.android
directory was owned by root. I removed the keystore file and also changed ownership to me (sudo chown -R $USER ~/.android
), killed the adb server and plugged in my phone, and it worked.
It was probably the ownership thing. Make sure you have read/write permissions in ~/.android