Are you sure it's not only a problem with Linux? No issue with my QC35 and macOS, Windows 10 and Android, always connects to my devices, albeit a little slow to connect sometimes.