I am trying to unlock my Nexus 7 (2012)'s bootloader running Android 5.1.1 on Ubuntu 12.04 (Desktop).

I am able to communicate & send commands to the device using adb (USB-Debugging on Nexus turned on - Android SDK & Fastboot tool installed on Ubuntu):

niq@vb-ubuntu:~$ Android/Sdk/platform-tools/adb devices
List of devices attached
015d2a4ffb401e0c    device

and the following command does the expected job aswell:

niq@vb-ubuntu:~$ Android/Sdk/platform-tools/adb reboot bootloader

After setting my tablet to fastboot mode I can communicate with it using the fastboot commands:

niq@vb-ubuntu:~$ sudo fastboot devices
015d2a4ffb401e0c    fastboot

However when I now try to unlock the device's bootloader, that is when I run into troubles, first try does the following:

niq@vb-ubuntu:~$ sudo fastboot oem unlock
...

When I open another terminal now and try it another time I get the infamous "waiting for device" message displayed in my terminal:

niq@vb-ubuntu:~$ sudo fastboot oem unlock
< waiting for device >

Same thing happens when I login as root rather than using sudo. And also doesn't make a difference if I use this command (also results in waiting for device):

niq@vb-ubuntu:~$ sudo fastboot oem get_identifier_token
< waiting for device >

My Ubuntu clearly is able to talk to the tablet and execute commands on the device, why is it not possible to unlock the bootloader given that it is recognised and all the other commands work seamlessly?

Another thing I tried:

niq@vb-ubuntu:~$ lsusb -v | grep Google
Couldn't open device, some information will be missing
Bus 001 Device 004: ID 18d1:4e40 Google Inc. 
  idVendor           0x18d1 Google Inc.
  iManufacturer           1 Google, Inc

/etc/udev/rules.d/11-android.rules:

UBSYSTEMS=="usb", ATTRS{idVendor}=="18d1", MODE="0640", OWNER="mbp"

and finally:

niq@vb-ubuntu:~$ sudo service udev stop
udev stop/waiting
niq@vb-ubuntu:~$ sudo service udev start
udev start/running, process 2424

Am I missing something here?