So, I tried a lot of different ways of doing this.
First, make sure your user is in the bluetooth group.
$ sudo usermod -G bluetooth -a <your_username>
Restarting your bluetooth service (and making sure it is enabled to start on boot) should be the next thing you try after checking the rfkill status - see other answers here on that.
$ sudo ...