Recently people have been reporting that the Screensleeves album art screensaver is displaying some information (track name, artist, album) but not all (album art is missing, time elapsed/remaining) when using the Spotify player.
Recently there has been a problem where Screensleeves has been unable to detect that Spotify is playing (and displaying the 'Paused' message). If this is your problem then the problem is at Spotify's end and here is the workaround.
The newer problem involves Screensleeves recognising that Spotify is playing and some information being displayed, but not the album artwork and certain other information. This latest problem is also at Spotify's end, they are aware and say that they're working on it.
Screensleeves is capable of fetching album artwork from the web if none is supplied by the player, though this may or may not be kicking in. I suggest checking Screensleeves' options in System Prefs and making sure that 'If no artwork is available' is set to 'Attempt to find cover image from the web'.
Once again, I hope that Spotify will be fixing the problem soon and things will be working as they should once more. Through all of this, other music players have been working fine as far as I'm aware.