Same problem here - tried all the "fixes" suggested by Samsung and other people on the Web, but nothing has worked so far.
Guess the next step will be visiting a Samsung service center
I did get mine to work after a day or so.
Seems they dont always work out of the box due to battery just being too drained.
As the left bud was the one not connecting - I worked on that one only
If you place it in the charging box and the light goes from red to green in just a few seconds - it means the bud is charged. But in this case the bud did not work, so this was a false reading.
I played around with the left bud in the charging box until the light stayed red.
Then I put the charging box aside for a few hours.
From the battery level of the box it was clear that it started charging the left bud.
After 2 hours I placed the right bud in the box as well and plugged the box in to charge.
After a few hours both buds were fully charged.
I unpaired my buds on the phone.
Reconnect by opening the box and following the steps for pairing.
This time both connected and all was fine.
So be patient and give the buds enough time to charge.