I had the same issue with my Spotify account. I tried everything (uninstalling/reinstalling, linking from my laptop, signing in on the PS4, etc.) I contacted Sony Support with no help. Finally, I contacted Spotify Support and was able to get some help from Juanito.
I created my Spotify account through my Facebook- which Juanito said has been shown to be an issue when linking with the PlayStation Network. He recommended that I create a new Spotify account through an email. Normally, I'd be frustrated at this, but he was able to move all my playlists, saved music, and followers from my old account to the new one. He also added in a free month of premium for the inconvenience.
Sure enough- I went onto the Spotify app from my PS4 and logged on using my credentials (not through the Spotify Connect option), and all is now connected and working fine. I went back to my account and linked my Facebook to it again- so everything is pretty much the same now- and it continues to work on my PS4.
A little bit of a complicated solution, but this was the only thing that worked for me. Hope this helps!
I FINALLY figured it out. If you have had a PS3 or another PS4/PS4 account that you’ve linked your Spotify to you have to go on that account directly and log yourself out of Spotify via the App. I had logged into Spotify on my PS3 over 2 years ago and only after logging out on it was unable to link my Spotify to my PS4