After leaving the kindle with the wifi on and in sleep mode it seems to be fixed.
When I turned it on again I noticed that the hour had changed (although it isn't the correct one, I manually changed it afterwards) and the sort by recent function was working again.
So if someone has this problem I guess the solution is turn on the wifi and put the Kindle to sleep for some time. Maybe enough time so it indexes all the books?
Not sure if the factory reset is needed tho, guess you have to try.