I didn't see the exact problem you've all mentioned, but my wife and I both had issues with the Kindle app after the latest upgrade.
After the upgrade it wouldn't let us open books, saying that the device wasn't authorized (even though we'd bought the books on our phones and had already started reading them).
Going to the 'Manage you Devices' page on Amazon.com, it showed that we each had both a 'PC36100' and a '2nd PC36100'. Evidently the upgrade makes the Kindle software think it's on a new device. We authorized the new devices and then used the website to 'deliver' the books to the new device. Then after a quick sync in the Kindle app on our phones, we were able to access all of our books again.
Probably worth a try to see if it fixes your problems too.