Hi Dan,
I’m running Playa, though I’m not sure whether that directly affects categories. And anyway, I experienced the problem before installing Playa… so I suspect that’s not the cause.
If I click on “edit categories” in the Publish page, and then click “done”—the categories will revert to being correctly ordered. But that’s a bit of a nuisance to have to do every time I post an entry.
The original bug discussed in the resolved thread (linked to above) from 2010 was also difficult for the EE staff to replicate, so it seems like it might be a bit of a slippery bug to pin down.
astuteo said he applied the 2010 hotfix and that resolved the problem. I tried applying the fix also, but it caused my admin::channel administration::categories page to go entirely blank. I think that may be because I don’t know enough (nothing) about php so I may have done something wrong. Anyway, I reverted to the original admin.content.php file.