Originally Posted by HarryT
Incorrect "Most Recent" sort order is generally caused by the Kindle's clock not being correctly set. Connect to WiFi or 3G and leave it connected for at least an hour. That should set the clock from Amazon's servers.
Yes, this fixed the problem for me on Kindle Touch (Thank you MobileRead search!) a while back and would hopefully fix it for the Paperwhite.