adb can find device but fastboot cannot
The problem with my device not showing up with the fastboot devices command resolved itself. I was then able to flash a custom recovery.

The only thing I did different was, I rebooted my computer and symlinked the adb and fastboot commands in my bin folder.