First off long time lurker first time poster here.
I got one of these kindles from the sale and was able to get root. I've unrooted and tried again and got root again so there are two different problems. 1 - Sometime superuser.apk doesn't get installed and 2 - The Play market doesn't get installed. I used 2 different methods to over come this. hopefully they'll help.
First steps to root with Kindle Fire Utility 0.9.5
1 - With the kindle not connected run the install_drivers.bat
2 - Connect the kindle and push disconnect when it comes up
3 - Run option 2 - "Install Permanent Root with Superuser"
4 - Run option 5 - "Install Latest FireFireFire"
5 - Run option 3 or 4 - "Install Latest TWRP/Clockwork Recovery"
Once those 5 steps are done you have 2 options to get superuser and play market
Option 1 (Easiest)
Since you now have FireFireFire and a custom recovery simply wipe and flash pre-rooted 6.3 rom This is the one I used [ROM] Stock rooted 6.3
Once that is flashed run Kindle Fire Utility again and in the Extra menu run option 5 - Mount Read/Write
Then run option 1 - Install Google Apps / Go Launcher EX
This is the easiest method the rom is already rooted and has busybox seems pretty fast too.
Option 2 (More involved)
After the initial 5 steps:
1a - run the extras option and Install google Apps / Go launcher EX (the last three will fail but that's ok)
1b - close Kindle Fire Utility and open a command prompt (start button type cmd)
2 - In the command prompt type: "cd " now drag and drop the tools folder that is inside the Kindle Fire Utility folder. (make sure you put a space after cd before you drop the tools folder on the command prompt.) This will auto fill in the path to tools folder. Push enter.
3 - Type "adb install " Drag and drop Superuser.apk located inside the files folder of kindle fire utility. This auto fills the path to Superuser.apk and push enter
4 - Now you need to install a root file explorer of your choice. I used ES File Explorer. *Important* the version of ES File Explorer from the amazon market is too old and will not work. Go To: http://www.estrongs.com/en/download.html
and downloaded the latest version.
4b - Install the .apk you just downloaded by typing "adb install " and drag the .apk from your downloads folder and drop it on the command prompt and push enter
5 - Now you need to enable your kindle to drag and drop files to it. On the kindle: Tap the top status bar and tap "USB is Connected"
6 - go to the Kindle Fire Utility directory -> apps -> system. In this folder there are three .apk's GoogleCalendarSyncAdapter.apk GoogleContactsSyncAdapter.apk and Vending.apk Copy all three to the root of your "sdcard" on your kindle. (Drag and drop to your kindle)
7 - On kindle tap disconnect. You should see ES File Explorer icon on your carosel Tap to open it. In ES File explorer Tap menu at the bottom and tap settings.
8 - Under "Path settings" Check the box "Up to Root"
9 - Under "Root settings" Check the box "Root Explorer" Tap "yes" on the popup and tap "allow" on the super user window.
10 - Under "Root settings" check "Mount File System"
11 - now your ready to copy the files. Tap back to go back to the sdcard. Tap "Select" on the top toolbar. Select by taping the three .apks you copied over. Once all three are selected Tap "Copy" on the top toolbar
12 - Tap "Up" on top toolbar. Tap "system". Tap "app" and Finally tap "Paste" on top toolbar.
13 - Reboot your kindle and you should now have the Market working on your kindle.
Note this is what worked for me. I've done it both ways as well as rooting with out Kindle Fire Utility and just jcase's method. Regardless of the method to root one of these two methods were required to get market running.
Hope this helps someone.