Fixing it is a breeze if you've already done it once. Just re-follow these instructions to get your market back up and working. Once again, Props go to Bandage for writing these easy to understand and follow instructions.
Root your Kindle Fire
Download the following apks
Vending.apk (Latest Version 3.3.11)
See HERE for .apk downloads (complete GApps zip file)
Root Explorer App (or similar that lets you change ro/rw permissions)
Side Loading Apps activated on Kindle Fire
On the Kindle Fire Settings screen, go to “Device” and turn On “Allow Installation of Application From Unknown Sources”
1. Transfer the .apk files to your Kindle Fire via PC / Mac (remember where you put them)
2. Open Root Explorer App, and navigate to the transferred .apk files
3. Select the GoogleServiceFramework.apk and install
4. When complete, click "Done" and return to the file location for Vending.apk
5. Long-press Vending.apk and select the "Move" option on pop-up menu
Navigate to /system/app folder
6. Change mount option from RO to RW (read-only to read-write)
Paste Vending.apk into the /system/app folder
7. Long-press Vending.apk and select "Permissions" from pop-up menu
Change permissions to match all other apps in this folder (rw-r--r--)
8. Install Vending.apk
9. Reboot your Kindle Fire
Once reboot is complete, select Market App and log-in as usual.
You will most likely notice some familiar apps missing from the market, as this device is lacking certain hardware specifications. However, once custom ROMs start appearing for the Kindle Fire, it is a safe bet it will no longer be the case.
Also, the Market App will not show up in the default Amazon Launcher.
You will need to install an alternate launcher (ie Go Launcher EX, ADW).
Find instructions HERE.
For another option than installing an alternate option, check out this work around also!