I already had libusb-dev installed. My system is 64 bit, so I also installed the 32 bit library, libusb-dev:i386, but still stuck at the same prompt
Edit: Nevermind, it was my mistake. I tried to use ubuntu built in fastboot, which apparantly does not play nice with kindle. After using kindle specific fastboot script, its working now.