I have had a 520 for 3 months and had no connection problems with an LG G2 other than only getting sporadic text and call alerts which was tolerable. Just upgraded to a Samsung Galaxy S6. Pairs fine but the BT connection keeps disconnecting and reconnecting. It is so bad that that it won't stay connected long enough to sync or upload a ride. Paired my old G2 again without a problem. Seems to happen even if there is no ANT activity.
No problems with my S6
Try forgetting the phone on the garmin, and the garmin on the phone, and pair them again.
Clearly a Samsung issue. Connection was OK after I rebooted the phone, at least sitting on my couch with the 520 and S6 for an hour. Had the same problem in my car this AM.