Grooveshark with the
'Groovewalrus' desktop client is one 'alternative'
I've never felt I've been able to subscribe to the Spotify service, with the way they [currently] remove tracks at will (or make them unavailable), and the MANY mistagged tracks in their library ...if [like me] you care about last.fm stats like I do