If you hadn't paired anything else before, it's easier just to

rm -Rf /var/lib/bluetooth/<your mac address>

then cycle the power. In my case, I had to remove the battery as well. Then power on and go through the pairing process again. You may have to do this a few times to get it to work.

This is a known bug.