After spending over 5 hrs wit Kindle customer support. I decided to search on my own and I came upon this site. I fixed my Kindle DX with help from and here’s how I did it.
With all due respect guys, it has nothing to do with ATT's signal. My area is TMobile and I got my Kindle DX working.
What no one figured out, is that there is 2 patches for Kindle DX.
The first patch will upgrade your Kindle DX to version 2.5.8, it is called (Software Update 2.5.8). If it is already updated, you do not need to repeat the first step.
The second patch is a service update (This is why is say's there is no certificate, and that one is called (Services Update). It is the second update that will connect your Kindle DX to Whispernet, update your certificate and it will allow you to register it.
I went to the following webpage that eschwartz posted. Thank you very much eschwartz, I do appreciate it. Below is the webpage,
http://www.amazon.com/kindlesoftwareupdates/dx
Good luck guys. This worked for me and it will work for you.