Instead of forcing permissions via sudo each time you need to run fastboot, you can permanently fix the issue:
- use lsusbto identify your device USB VendorID
- configure udevto set proper permissions when your device is plugged in
- profit!
As a bonus - it  will be fixed for adb too.
For example, in my case (for 'Megafon SP-A20i') :
$ fastboot devices
no permissions  fastboot
$ sudo fastboot devices
[sudo] password for kaa: 
MedfieldA9055F28    fastboot
$ 
Let's fix:
First, we need to identify the device:
a) look for usb bus number (hack: I know the device is Intel-based one)
$ fastboot -l devices
no permissions         fastboot usb:1-1.2
$ lsusb |grep 001 |grep -i intel
Bus 001 Device 044: ID 8087:09ef Intel Corp. 
Bus 001 Device 002: ID 8087:0020 Intel Corp. Integrated Rate Matching Hub
$ 
b) look for other Intel devices: 
$ lsusb |grep 8087
Bus 002 Device 002: ID 8087:0020 Intel Corp. Integrated Rate Matching Hub
Bus 001 Device 044: ID 8087:09ef Intel Corp. 
Bus 001 Device 002: ID 8087:0020 Intel Corp. Integrated Rate Matching Hub
$ 
Hubs are not smartphones definetely, so - USB vendorID we need is "8087".
Second, configure udev (you must replace "idVendor" value with yours) :
$ sudo sh -c "echo '# Megafon SP-A20i' >> /etc/udev/rules.d/51-android.rules"
$ sudo sh -c "echo 'SUBSYSTEM==\"usb\", ATTR{idVendor}==\"8087\", MODE=\"0666\", GROUP=\"plugdev\"' >> /etc/udev/rules.d/51-android.rules"
$ sudo service udev restart
udev stop/waiting
udev  start/running, process 1821
$ 
Third, re-plug your device to allow udev to perform it's magic.
Final check:
$ fastboot -l devices
MedfieldA9055F28       fastboot usb:1-1.2
$ adb devices
List of devices attached 
$ fastboot reboot
rebooting...
finished. total time: 0.253s
$ sleep 90
$ adb devices
List of devices attached 
MedfieldA9055F28    device
$ 
Voila!