The short version of the page linked by D Shu (and without the horrible popover ads) is that this "waiting for device" problem happens when the USB device node is not accessible to your current user. The USB id is different in fastboot mode, so you can easily have permission to it in adb but not in fastboot.
To fix it (on Ubuntu; other systems may be slightly different):
Run lsusb -v | less
and find the relevant section which will look something like this:
Bus 001 Device 027: ID 18d1:4e30 Google Inc.
Couldn't open device, some information will be missing
Device Descriptor:
...
idVendor 0x18d1 Google Inc.
Now do
sudo vi /etc/udev/rules.d/11-android.rules
it's ok if that file does not yet exist; create it with a line like this, inserting your own username and vendor id:
SUBSYSTEMS=="usb", ATTRS{idVendor}=="18d1", MODE="0640", OWNER="mbp"
then
sudo service udev restart
then verify the device node permissions have changed:
ls -Rl /dev/bus/usb
The even shorter cheesy version is to just run fastboot
as root. But then you need to run every command that talks to the device as root, which tends to cause other complications. Simpler just to fix the permissions in the long run.