Same here. (Coming from s6 too) Working with and repeatedly failing at Bluetooth connections is the #1 way to turn me into a murderous banshee. I can't get it to work at all (all I really care about is calls which I need to be able to get hands-free while driving.) I think it's a problem with the phone because it's beeing twitchy about the connection to my wireless headphones also. (connects, sometimes plays for a long time--sometimes 30 sec--before disconnecting ad nauseam, s6 was perfect.)
Reporting back to say: fix was really easy and dumb. The bluetooth in my car had too many devices stored (including a motorola razr.) I deleted them and then easily paired the phone with the car. Whoops. Doesn't explain dropping my wireless headphones, but sure is a good start...