Stephan's answer works (using sudo adb kill-server), but it is temporary. It must be re-issued after every reboot.
For a permanent solution, the udev config must be modified:
Witrant's answer is the right idea (copied from the official Android documentation). But it's just a template. If that doesn't work for your device, you need to fill in the correct device ID for your device(s).
lsusb
Bus 001 Device 002: ID 05c6:9025 Qualcomm, Inc.
Bus 002 Device 002: ID 0e0f:0003 VMware, Inc. Virtual Mouse
...
Find your android device in the list.
Then use the first half of the ID (4 digits) for the idVendor (the last half is the idProduct, but it is not necessary to get adb working).
sudo vi /etc/udev/rules.d/51-android.rules
and add one rule for each unique idVendor:
SUBSYSTEM=="usb", ATTR{idVendor}=="05c6", MODE="0666", GROUP="plugdev"
It's that simple. You don't need all those other fields given in some of the answers. Save the file.
Then reboot. The change is permanent. (Roger shows a way to restart udev, if you don't want to reboot).