@Irk I doubt thats true you probably have also a spotify account by registering an email and a pass and it so happens that the email you used is the same as the one you use for facebook and you also use the same password... because those (login credentials and facebook log in button) are two different things and are not talking to each other
E.g if you have not a spotify account but have a facebook account and NOT click on the "log in with facebook" button but use your facebook credentials to log in via the spotify login option then it wont allow you to log in.
@papajo Spotify didn't really tell me what the issue is they just asked me to let them know if I had any other issues I had another issue last night on one of my other PC's but didn't feel like going through the process of getting through it again it was late and I had to wake up today just got a new little cheapo laptop today and will be seeing what happens when I get Mint installed on it. I went through Twitter to reach out to Spotify they worked some backstage voodoo to get it fixed, it took them a bit but they did get it working for me on one system.
I have a fresh install of Ubuntu 16.04 and I got that same behavior. While this is a solution, it would be nice if spotify devs either: 1) be honest about it and remove the FB login button or 2) fix it.