It took me a while to troubleshoot, but it seems to come down to commas. When I sort by a lookup field, if a row has a comma anywhere in it, it sorts first, despite what it starts with.
In the original table they sort like this:
01 item
02 item
03 item
04 item, item
But if that field is the lookup and is sorted, it goes like:
04 item, item
01 item
02 item
03 item
Is this a bug or am I missing something?