照合順序が異なれば、並べ替え順序も異なり、ウムラウトの解釈方法も異なります。
例: utf8_general_ci は Ö を O でソートします。代わりに utf8_swedish_ci で試した場合。これは正しいソート順になります。これは (IIRC) ÄAÖ がアルファベットの最後に移動することです。
背景情報については、http://dev.mysql.com/doc/refman/5.0/en/charset-collation-effect.html および Mysql Unicode を参照してください。