@cardamon: Given your log, no, you didn't use the -3.2.1 jailbreak install. That's likely the root of your issues. Don't forget to restart your Kindle after the JB install, in case there's a bit of a mess of JB left after the previous uninstalls (some early versions behaved badly on uninstall, and left the system in an inconsistent state until a reboot)...
To answer the question about the error codes in details:
Yes, that's consistent with a non jailbroken device for the ss/usbnet hack (U007), and that's consistent with using the 'old' jailbreak install on firmware >= 3.2.1 (U004).
Thanks for the logs, btw, it's refreshing to actually have enough information in the first post to provide a definitive answer straightaway

.
Just to make sure: Did you uninstall the jailbreak at one point? Or just the other hacks?
@GM: Unfortunately, the 'UYK' link will light up with both JB install files, so we can't use that to avoid mistakes

. (It just checks the device code, so as long as there's a 'k3g' in the name of the bin file, it means it's tagged for a K3G [in this case, although it'd be pretty dumb to actually put a different tag in the filename than what the device code in the update header actually refers to ^^]).