After an upgrade, if you don't have Whispernet on to re-sync your Kindle's internal clock with the Amazon, the time stamp on your books gets reset to an old default system value. Hence, sorting by "Most Recent" puts these books last in your list. Turning on Whispernet cures this. Once your Kindle re-syncs its clock, open & close your books - and they will move to first on your list.
If you are not in Whispernet range, search this forum for threads on how to reset your Kindle clock using the USB connection to your PC.