exactly the same problem I got... when typing "fastboot devices", it comes out empty... but when i swapped the fastboot executable, it finally showed-up...
also... if you are using linux (or actually even a mac)... have you tried doing a "sudo"?
btw, I was using a linux (ubuntu) machine.
I'm using Windows XP