What Bluetooth adapter do you use? Some phones might be incompatible with internal Bluetooth adapter of Raspberry PI (based on Broadcom chip) and the only solution is to use external Bluetooth dongle (not based on Broadcom chip). Please remember to execute sudo btswitch external command when you will switch to the external Bluetooth dongle.