I had this problem and tried everything - re-formatting columns from alpha to numeric and vice versa, trying to sort small sections at a time, etc. I searched the Knowledge Base ad nauseum too but nothing worked until I stumbled upon this little workaround - or maybe it's just a kludge fix. Regardless, it worked.

1. First select the columns and rows you want to sort.
2. Highlight a column you DO NOT WANT TO SORT, then sort everything on that (which sorted correctly in my case)
3. Now, resort based on the criteria you want VOILA - IT WORKED, BUT DON'T ASK ME WHY.

Good luck.

Now I can get back to work doing something productive.