So far, the single biggest source of complaints has been the change to the PM count behavior. People have an unread PM on page 17 and the count never goes to 0, which they assume is a bug.
It seems that the simplest solution would be to offer a button to mark all PMs as read, thus dropping the count to 0.
It would also be helpful to have a view for unread PMs.
Probably not realistic for 3.1.0, but all the same.