I probably spent a full 4 hours trying to fix this last night and today. What a complete bunch of clueless people Amazon has working for them. I used to have a high opinion of Amazon, but all this mess changed it.
During my useless conversation with Will yesterday I mentioned that I had a Mac, but used VMWare to mount the user partition to erase the files in Windows, since I read on the Amazon forums that perhaps OS X (eg, Spotlight) had dropped a file on the partition that the Kindle had problems indexing. Today's conversation with support had the agent read back the notes from yesterday, and informed me that since I had used VMWare to installed unauthorized software on the Kindle, I had voided the warranty. She explained that since I had rooted (not true) the device, they could only offer a discounted replacement, but not a warranty swap. The sad thing is, I didn't root the Kindle, I don't have any interest in tinkering, I just want an e-reader. Lesson learned, play stupid when talking to support.
In the end, I was able to fix it, but it took some timing. I noticed that when the USB cable was plugged into the computer, there was a 0.5 second period between the USB energizing the card before the Kindle was enumerated in the OS, however if I ejected the Kindle from the OS, the screen saver went into its deep, un-wakeable sleep. During this time, the display was responsive to touch, but only for 0.5 seconds. It took a few turns, but I was eventually able to navigate to Settings -> Reset Device and get it to the factory settings. After it booted, things seemed to work fine.
Unfortunately, the second CSR today deployed a log gathering package that kept gathering logs and rebooting the Kindle every time I put the device to sleep. I called customer service a third time, and the agent recommend I do a new "Device Reset" to clear it out, which did work.
I don't understand why Amazon doesn't have a DFU restore like the iPhone, specifically for cases where something went wrong and you'd like to zero it out to defaults without navigating menus.
Hope this helps someone else!