vivoactive 5 won't connect to headphones

My brand new Vivoactive 5 will not connect to my Plantronics Backbeat 3200 headphones - although they connect just fine to my old Vivoactive 3. The headphones pair with the watch, but then when I try to play music I get a "searching" status and then the connection fails. Have tried all the usual troubleshooting. 

Tried to get Garmin support through chat, but the agent was less than helpful and just said maybe the headphones are incompatible with my watch. 

Anyone had similar problem? I love these headphones and would hate to have to replace them.

thanks!