A small tutorial when Facebook says Spotify is already connected and Spotify says it isn't.
Important!! You need to know your Spotify account details without your Facebook credentials. If you don't know these, please don't proceed with these steps.
Go to your facebook account and press the "down arrow" in the top bar (next to your profile picture). Choose settings.

When this is opened, choose apps.
In the next screen type in Spotify and select it.

In the lower part choose remove app.

It asks to confirm and when you did, it is deleted.
Now head back to Spotify.
You will be able to connect it to Facebook again as a new link.
[edit made because of Dutch screenshots. Now made in English]