Got the sorting fixed, thank you for the quick advice.
I set a new time from the menu (no date was possible to set) and it didn't work.
I briefly connected my Kindle to wifi and run sync. Then the sorting got fixed

(I think it changed the date)
As to how I got to the state where recent sorting didn't work was:
- Registered my kindle (fw. 5.6.2.1)
- Disconnected wifi
- Upgraded to fw 5.6.5
- Serial jailbreak device
I was planning to never connect my Kindle to the internet again. Had a nasty auto fw upgrade on my PW1