I am not on linux but I spent hours on this problem on a brand new Asus gaming laptop and I wish I could credit the original poster but it was a video that led me to this solution:
Hold down the power button for a full 60 seconds and it resets your bluetooth and wifi then restart. Completely...
