Hello there,
As far as I am aware, the Kindle Fire has a sort of "cut down" version of the Android Marketplace, and Spotify is not available on there. We do wish to be available on a large number of platforms, however, so the Kindle Fire might something we might look into in the future.
Airhorn Enthusiast