You need to add the Entered Queue column to your view (it's part of the Queue Item entity).
System views can only sort on columns on the view being shown, not on related columns. In your example above every column is part of the "Regarding" relationship, which may be a related Contact/Case/Activity/Opportunity/whatever. There's no guarantee that the regarding record even exists for each queue item, so it's not possible to sort by it.
"Entered Queue" is in the default view - just add it back and sort by that, and you'll get items added to the queue the longest time period ago float to the top of the list as you'd expect.