Recently got myself one of these phones and can't get my Edge 510 to sync with it.
I also have a Forerunner 920 XT and it pairs flawlessly.
I have tried unpairing and re-pairing as well as uninstalling the Garmin Connect app all together. The watch connects via Bluetooth every time, but the Edge 510 fails to sync.
With my last Android phone as soon as I turned on the Bluetooth (phone paired) the Edge 510 would flash up immediately "Phone Connected". Now I don't get that (bluetooth enabled on phone and Garmin)
Any ideas?