Murmur interferes with Bluetooth discovery
When Murmur (https://github.com/casific/murmur) has previously run on a device, it continues to run in the background and starts a background service on boot.
The background service seems to interfere with Briar's ability to discover other devices via Bluetooth. Log output shows that devices are sometimes discovered, but more slowly, causing Briar to time out before a connection is made.
Stopping Murmur's background service or uninstalling Murmur solves the problem.