Although they do sometimes fall down for consumers, I have a 2nd gen kindle bought from the US but running on the UK store which no longer talks to the store (I can download content but not browse).

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.