Have you find the solution? I am also in the same boat as you. Unable to register, but the device is registered in my amazon account.

yes, solved the problem:
on firmware 3.4.2 start chroot firmware 2.5.8, install the service update and then de-register the Kindle. Reboot, after on 3.4.2. buying book in store worked.

maybe there is a simpler solution, I don’t know.

I did something stupid, and I can't seem to find advice in this very long thread.
I was not able to install the update to back up my existing software, so I went blithely ahead and installed 3.1. The installation was a success, but now I am unable to register my DX. It is still listed as registered on Amazon.com, but it won't let me deregister. Attempting to register from the DX doesn't work. I get a message that it is unable to connect, and if I try to shop Amazon, I get a message that there is a problem with my account and to call Amazon. Before I do, I wonder if there is something I can do. I know I can't tell them that I applied a jailbreak and installed 3.1. It is not the end of the world, as I trying this to enable me to use 3G for Gmail, which was no longer possible with 2.5.8. I was able to buy books via 3G, but I don't use the DX for that, more for pdf and library books. I'll try to call and plead ignorance, but I doubt they can fix things! Otherwise, nice work!

If you continue the update process to the current 3.4.something, you will restore the ability to connect with Amazon.
There is a thread here on that topic (3.1 -> 3.4)

You will not find in any of the 3 series firmware the ability to connect with any site(s) that the Amazon proxy server prohibits.

Thanks so much. I'm not Linux-savvy or even computer savvy. I'll have to read up here! I really wasn't using browser anyway -- I upload books via Calibre.

Do you think I could stumble through the upgrade process? I've only done basic things like jailbreaks and font hacks. Maybe I'll learn something. Thanks so much for all of your help here knc1!!!

Hi. Is it possible to register a DXG with Firmware 3.1 or higher? (And to access his or her own library then.... ?)