Only savvy users could figure out that one needs to press the date, or arrived, twice in order to toggle the order of the messages up and down.
At least have the icon change, from a top heavy stack of books (laid flat), to a bottom heavy stack of books.
Otherwise, take the case of no messages in any mailbox. Well, how would the user know what sort order he has set up?
Also consider the case of a user who might have messed up the sort order and just simply wants to return to the default. Therefore consider adding to that menu some kind of indication of which one of the default was.
