Apparently the server needs to be started while in su, but I don't know how to access the adb path while in su, so I had to go:
Code:
cd ~/{android_sdk_folder}/tools
sudo su
./adb kill-server
./adb start-server
exit
now "adb devices" works, and you should have no more insufficient permissions errors. You have to do this every time you want to start an adb shell, unfortunately. (Well, i'm SURE there's a workaround, but I'm a *nix neophyte, so this is my solution).