As you mentioned in your problem, you can physically choose all the content. MANY people actually do the click in the range somewhere, then move to Sorting letting Excel choose the range sorted.
They'll swear all day long the proper range was selected, but along with not actually physically choosing the range, and so knowing for a fact it was really fully selected, they didn't even bother, after letting Excel choose the range, checking to see that Excel picked the entire desired range. Even after you ask them to, they'll still not do so and swear the full range is selected while not really knowing so.
GLAD you are NOT unsensitive to that! The two answers refer to this problem.
But since you physically select the correct range and it still doesn't seem to sort properly, one can move onto the next thought.
Many formulas return material from another place based upon their location in the current material. Not saying that well, so try this: A formula in cell F1 might look to an entirely other spreadsheet even, in that spreadsheet's cell A284. When column F's cells are sorted, they really sort, but in the end, cell F1 still has a formula that looks to the other spreadsheet's cell A284. After the sorting, after Excel adjusts the moved formulas for their moves. So the sort worked, but now the sought data does not match what's in cells A1:E1. Those cells had text, let's say, and moved about. F1 moved about as well, but after doing so Excel adjusted its formula for the move and cell F1 still ends up referring to cell A284, so it does not match.
This is surely the difficulty that you face. Note that it need only be a single cell in each row, if others to its right (usually the way things lay out, but some to its left could look to it as well) look to it for their own formulas.
So maybe A1:E1 have text typed by a user. Then F1 refers to the first row of some data range, beginning in A284. F2 refers to A285 there, and so on. Cell G1 has a formula that takes F1 as a lookup value and finds something in some place, the same data range or maybe some other even. And so on. So ONLY F1 is a problem. Fixing its formula to no longer find a precise address in the other data range will then solve the problem. Mind you, it's OK for it to find the same precise DATA, perhaps by looking to its left in the textual A1:E1, just not for it to look at the same exact ADDRESS in order to do so. Then the rest to its right will use the new value found to find their contents. When sorted, F1 no longer looks for A284, but rather at whatever value the cell to its left, say, cell E1, has. Since that changed in the sort, so will F1's contents and it will appear to have sorted properly.
So, look for formulas like that, ones that look at an ADDRESS or do a lookup, perhaps, that does not depend upon other content in the row. Fix them so that they might look for that same DATA, but via perhaps a lookup that depends upon stuff in their own row, not upon the physical address of some cell in the target range.
Levels of stuff pile up in Excel and cause fairly subtle effects as you layer things on. This is surely an example of that.