Bad news: Spotify no longer works on the 1st Generation Kindle Fire. You can try to download it from the Amazon App Store, but it won't install. You can try to sideload the app from an APK, but the installation will fail. You can try to install an older version of the app, but it will insist you use the most current version.
I've looked, and this hasn't been addressed anywhere by Spotify or Amazon, despite hundreds of one-star reviews of the app at Amazon from users who can no longer run Spotify on their Kindle Fire.
You are right. Unfortunately Amazon haven't updated the KIndle Fire (2011) past Android version 2.3.3 (Gingerbread). It does seem odd that they have let this one go and unfortunately Spotify have had to discontinue support for Gingerbread & Honeycomb support; see announcement here.
I'm afraid you have 2 options:
1. Remain on the official ROM and lose Spotify as well as a continuing volume of apps which are also discontinuing their support for anything prior to Ice Cream Sandwich.
2. Root and use a custom ROM (I believe there is an ICS ROM for the 1st gen Fire), Be careful if you do try this and make sure you read up fully prior to doing it to understand the risk involved.
I'm sorry, this isn't good news and I do feel that Amazon have let the original fire just go without giving further support to the users who did have it.
Please use the search feature before posting a problem/bug/idea. What's a Spotify Rock Star, and how do I become one? Using Spotify Since March 10th 2009 Twitter: @mechanimal82