http://www.spotify.com/int/blog/archives/2010/07/12/linux/ says they have a preview version of a native client, at least for premium subscribers. It lacks local mp3 playback, though.