I have the same problem, nothing is working to get rid of it. It's just a joke, that this bug is around for such a long time, i honeslty think that spotify does not even care about this. In the words of a famous orange man this is just "SAD".
Wow I can't believe I still can't use this feature even after I change my phone twice in the past year....Spotify you better get it together. How come others can do this and we can't? What's the difference?
I think this has something to do to the fact that Instagram is native to Galaxy phones now (or after some of the updates last year). I can't unninstall it anymore, just revert back updates. Maybe it's conflicting with something and Spotify is not being able to identify and link stuff. I can't think of anything else because it's such a huge chunk of people being left out.