fastboot not working on my Nexus 4
The clue lies with the comment above But I just tried 'adb reboot bootloader', and it worked. which shows that adb is indeed recognizing the USB connection, but not in fast-boot mode which is where this answer comes in...

Sounds like the udev rule for the fast-boot is absent!

Do this: lsusb with the cable plugged in while the handset is in fast-boot mode.

Typical output should be one similar to this:


  Bus 001 Device 012: ID 18d1:d00d Google Inc.

                     ^^^^ ^^^^



The numbers identifier 18d1:d00d corresponds to idVendor : idProduct respectively.

Make note of it, and check your udev rules found in /etc/udev/rules.d/51-android-rules. (Mileage will vary slightly with differing Linux distributions!)

If you do not have this file, then its recommended to create one using root, there may be a few rules that need to be added depending on the mode of the handset, i.e. normal, recovery and boot-loader modes.

Here's an example of mine, that has differing values respectively when handset is in one of these modes. Take this as a template and change the numbers as shown that matches up with idVendor and idProduct respectively to suit your make/model of handset.

SUBSYSTEMS=="usb", ATTRS{idVendor}=="19d2", ATTRS{idProduct}=="1354", MODE="0666" GROUP="androiddev", SYMLINK+="android%n"
SUBSYSTEMS=="usb", ATTRS{idVendor}=="19d2", ATTRS{idProduct}=="1350", MODE="0666" GROUP="androiddev", SYMLINK+="android%n"
SUBSYSTEMS=="usb", ATTRS{idVendor}=="19d2", ATTRS{idProduct}=="1351", MODE="0666" GROUP="androiddev", SYMLINK+="android%n"
SUBSYSTEMS=="usb", ATTRS{idVendor}=="18d1", ATTRS{idProduct}=="d00d", MODE="0666" GROUP="androiddev", SYMLINK+="android%n"


The user id is added to the androiddev group, which was created on previous occasion, in that way I do not have to sudo at all! 

To create a group, using root


groupadd androiddev, this creates a group, then to add your
linux's user id to that group...
usermod -a -G androiddev your_user_id; replace your_user_id with your own user id used for logging in).


Then when in fast-boot mode, the fastboot binary should work (bonus! without the necessitating for sudo either!)