Hm, if you did a format did you remember to install all the drivers that pertain to your machine? For example, I have an ASUS laptop and whenever I've done a format (which sometimes is nice too) I always make sure to grab the latest drivers for the specific model of my laptop at the ASUS website.
After I'm completely done updating Windows updates. NOT installing anything else, I'll install those specific ASUS drivers. I've had Bluetooth issues just like yours after a format and it was because I didn't install the ASUS drivers. After installing the drivers one at a time, restarting, updating, I'll move onto the next driver.
I don't know if this is the best method but it's worked for me. Because I was able to figure out what drivers/parts were messing things up, stop, research it on a tablet/my phone, get the fix, then move onto the next driver. And after that long arduous process, I'll install my 3rd party software.
Hope this helps, let us know the outcome.