"The kindle store is gone

"
I currently have that same problem, my DX-G is on 3.1 firmware but got indication of available firmware update. I made the error of clicking Ok instead of Cancel, and it then did the update. Indeed access tot the Kindle Store is now gone. It tries to connect but fails. Error is "Your Kindle is unable to connect at this time". Browsing amazon.com or amazon.co.uk still works (using http, so the problem with the store is probably an https protocol issue ?)