In other words, if I click on username to sort them alphabetically, the names display fine on page 1, but on page 2, it changes and shows the user accounts recently created. I have to click on the 'username' link again on Page 2 for these names to disappear and the correct sorted list to show.

To replicate:

1.) Add a few user accounts as usual
2.) Assign a role to the new accounts
3.) Sort by that role first, then sort on username
4.) Click on page 2 - you can see the newly created user accounts at the end of page 2