On the desktop applications, try going to Preferences -> Playback and turn off High quality streaming, and then restart Spotify. Does that solve the issue? If not, try doing a clean reinstallation by following the steps outlined here.
It's also possible that it's an 802 error, which normally means it's a temporary database issue. Spotify normally automatically fixes 802 errors within 24 hours.