I’ve packaged (and will probably make newer packages as newer builds arrive) the Spotify client for Red Hat Enterprise Linux 6. There is probably not a lot of “private users” using Rhel 6 Desktop, since it’s more a corporate distribution, but hey ! working people also want Spotify ;) The package should probably work on Fedora as well, however I leave no guarantees, if it doesn’t, feel free to rebuild it. You can grab the spec-file here. The package is built with Gnome-support and should integrate nicely with menus and Spotify url’s.

Edit 20140107,
* There is a better way nowdays, use the “old method” (the new method is only working in fedora atm) described here