Is your clock correct? I was finding in my multiple reboots (with the old firmware) that I would lose the clock setting most times. If the clock is not correct, "most recently used" doesn't work properly.
If you've actually lost your collections, I've seen some references to de-registering/re-registering your Kindle to force it to re-download the collections that have been synced to Amazon.
Good luck
