When the Kindle Fire HD came out, Open Star Map wasn't compatible with it, so Amazon removed it from the Appstore. I couldn't fix the problem with Open Star Map because my development laptop wasn't fast enough to run the Kindle HD emulator for debugging and I didn't want to buy a Kindle HD just to debug a free app.
Anyway, I now have a faster development laptop, so I was able to fix the problem. The problem was that the Kindle HD reports having a compass but doesn't.
Anyway, here's the app.
Open Star Map is basically the open-sourced code from the Google Sky Map, with some modifications to make it run a little better on Kindle Fires.