Some distros have difficulty recognizing USB devices. After powering up in bootloader mode and connecting your phone to your computer, open a terminal and enter:
echo 0 | sudo tee /sys/bus/usb/drivers_autoprobe
After this, click "unlock bootloader" button on the graphene site. A popup should appear, allowing you to select the phone and grant access.
This elimates a Gnome bug in some distros. This may do the trick.