So, I was apparently talking garbage earlier. My bad and sorry for the confusion.

I've verified that things (as in footify using libdespotify) work with a premium account, and nothing is acting up.

(I was fooled by the error message, "Key exchanged failed", this has earlier, as far as I know, indicated problems on the protocol level.)