[Nexus 4 Q&A, Help & Troubleshooting] starscream92:
Hey, I have a Ubuntu 12.04 LTS machine and successfully unlocked my N4's bootloader and rooted it, but it shouldn't make any difference. Can you post exactly what the following command (which I assumed you entered, without the $ prompt) outputs:

$ fastboot oem unlock

Setting up your PATH

Also you need to make sure adb and fastboot executables are in your path. I can help you do that:

Open up .bashrc in your home folder with your favorite text editor (mine's gedit, without the $ prompt):

$ gedit ~/.bashrc

Add the following lines:

export PATH = ${PATH}:/home/username/android-sdk-linux/platform-tools/
export PATH = ${PATH}:/home/username/android-sdk-linux/tools/

Note:

You need to put the directory where you installed the Android SDK on your machine correctly. The paths above are just examples in my case and probably won't work for you.

Save and exit gedit. Close every Terminal window you have and open up a new one. Test by typing in (without the $ prompt) with an Android device plugged in and USB Debugging checked:

$ adb devices

Setting up the udev service

Once you're sure adb and fastboot are in your path, you also need to add the extra udev rules for Fastboot and ADB (in recovery) to work. To do that:

As root, create a file called 51-android.rules and put it in /etc/udev/rules.d/ (again with gedit, without the $ prompt):

sudo gedit /etc/udev/rules.d/51-android.rules

Copy and paste the following contents into the file:

SUBSYSTEM=="usb", ATTRS{idVendor}=="0bb4", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0e79", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0502", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0b05", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="413c", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0489", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="091e", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="18d1", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0bb4", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="12d1", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="24e3", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="2116", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0482", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="17ef", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="1004", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="22b8", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0409", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="2080", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0955", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="2257", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="10a9", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="1d4d", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0471", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="04da", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="05c6", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="1f53", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="04e8", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="04dd", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0fce", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="0930", MODE="0666"
SUBSYSTEM=="usb", ATTRS{idVendor}=="19d2", MODE="0666"

Save and close the file. Then, run the following commands (without the $ prompt):

$ sudo chmod 644 /etc/udev/rules.d/51-android.rules
$ sudo chown root:root /etc/udev/rules.d/51-android.rules
$ sudo service udev restart
$ sudo killall adb

Disconnect and reconnect your device (making sure it's in Fastboot/bootloader mode) and run the following command (without the $ prompt) to test:

$ fastboot devices