Things to try:

• Make sure Bluetooth tethering is on. 

• Make sure Location services are on. 

• Make sure Wi-Fi is off (on Androids) 

• Make sure hotspot is on (on Apples)

• Try updating the phone's OS to the latest release.