Can't find previously connected device

So I’m trying to connect my Bluetooth headset to my phone. I’ve connected it before, then used my headset with a different device (my tablet), but now I want to go back to my phone.

Short and simple, I’ve connected my headset before to this device, so I know it’s supported in some way. And I want to connect it again.

So, I go to the smartthings connect (“Add a device”) screen. (For whatever reason there isn’t a “Headset” option out of all the devices) So I click the “Auto detect” button (just like I did before) I put my headset into pairing mode and nothing shows up.

Extra notes:
My Bluetooth headset is a Trekz Air
The device doesn’t show up in my device list.
My phone is a Samsung note 5