I had the same issue and was able to get around it with some tinkering. I'll offer a recap of what I did below that assumes a high level of ability on your part. I can offer you no great assurance that these steps are complete or entirely accurate, so don't do this if you aren't confident that you are competent (or you otherwise won't be bothered if you turn your Kindle Fire into a brick). Some of what I did was probably not necessary such as clearing the application data for all of the Google apps on the Kindle Fire. Hopefully someone more capable than I can use this to come up with a cleaner and more concise method of dealing with this problem.
Using a file explorer (Root Explorer) I found a SQLite database at: /data/system/accounts.db
I copied the accounts.db file to my /SDCard/ folder using the file explorer.
I then edited it with a SQLite editor app (SQLite Manager) and altered the accounts table by adding a new row.
On that new row I added the next record number in sequence as the new ID (3 in my case), the email address of the alternate Google account I wanted to use as the Name, and com.google as the type. I left the password field blank.
I then browsed to the /SDCard/ folder with the explorer and copied the altered accounts.db.
Then I browsed to the /data/system/ folder, renamed the existing accounts.db file to xaccounts.db, pasted the altered accounts.db file, and then altered the permissions of the altered accounts.db file to match the permissions of the original renamed xaccounts.db file.
I then cleared all application data for all Google related apps on the Kindle Fire and shutdown and restarted.
When I opened the Android Market it prompted me to accept the license agreements again and was back in the Android Market with my original account.
I then opened the menu and select Accounts. I was then presented with the Choose Google Account dialog and my new account was listed as an option.
I selected the new account and entered the correct password. I was then able to operate in the Android Market with the new account.