You need to repeat the process of loading in linux the android udev ids, but for the bootloader stage (yeah, they differ)
# rebooting into fastboot mode
adb reboot bootloader
# grab you fastboot/bootloader device ids
lsusb
> Bus 001 Device 035: ID 18d1:d00d Google Inc.
# install the ids into /etc/udev/rules.d/99-android.rules
SUBSYSTEM=="usb", ATTR{idVendor}=="18d1", ATTR{idProduct}=="d00d", MODE="0666", OWNER="thiago"
# restart udev
/etc/init.d/udev restart
# try fastboot
fastboot devices