This probably only happens to me and every time this stumps me is because I do it so infrequently that I forget that the fix is simple but when I sort the users list by a different field other than name the ABC short cut bar disappears. In any org with more than 50 users you need this to quickly and efficiently find users to check or make changes.
To recreate go to Setup -> Manage -> Users and select a column to sort other than name this is what your screen looks like.
Now to fix click the full name column and viola! They are back, crazy but every time I do it it takes me a bit to realize what I’ve done.
And really, without the last name search bar I’m lost and have to use the search to find users. And no matter what view you click it will not come back. Simply but now you know.