I've resolved this.
The problem was that the horde horde_sessionhandler table was broken.
I think this was caused by a mysql update a few months back that nuked all of the innodb tables on the server (what a great day that was).
So what I did was:
Now message sorting preferences are remembered and the Last Login text is working too.
mv /usr/lib/mysql/horde /usr/lib/mysql/horde.backup
(in mysql client) create database horde
from the command line: /scripts/fullhordereset
That last command recreated the horde database.
This worked for me. I don't know where users address books are stored, so this solution might nuke people's address books, and so a less destructive approach might be to just delete the files in /usr/lib/mysql/horde/ for the horde_sessionhandler table and the recreate that table (although I'm unsure where the sql for that might reside).