Say what you like about Amazon, but you must admit that they are a very shrewd company. Provide fantastic customer service to the consumers, and almost none at all to the sellers. Brilliant.
I ended up in a maze of the US folks saying it's a UK store problem and the UK folks saying it's a US supplied kindle so talk to the US. After a few rounds of "reset back to factory" support calls I gave up.
I suspect the problem is the clock which is out by an hour so SSL / authentication isn't working. I held out until we left summer time back to GMT but even then it was still broken (I also tried from the Caribbean in case it was a European time zone issue). The GSM modem diagnostic page looked correct.
In the end I gave up and my partner got me a Kindle Oasis from Amazon UK for Christmas.
Iirc they were disabling some old SSL stuff (either sha1 or weak ciphers) that the old firmwares relied on. If that's your problem you just need to manually update and it should work again.
I ended up sending an email to jeff@ asking for an exchange of the Kindle to a US one. Ended up getting a one-time credit for the cost of a new Kindle with 3G.