おかしくなった並び順は規則性は無くランダムですか？
プラグイン以外に直接カスタマイズ等はされていない状況でしょうか？
あと、ページごとに表示順が入れ替わって表示される事はありますか？
例えば、
管理画面「商品検索」ページの「カテゴリ」
管理画面「商品登録」ページの「カテゴリ」のカテゴリの並び順は揃っていますか？

ご確認、よろしくお願いします。