恐らく自己解決しました。

いろいろな問題と複数の形式でのトラブルだったので、すべて解決したかどうかはまだわかりませんがとりあえずwmvやavi形式のものは安定しているように思えます。
端末から

gstreamer-properties

と打ち込んでマルチメディアシステムセレクタを起動し、ビデオのプラグインを「Xウィンドウ・システム(Xv なし)」に設定しました。

それなら↓に詳しく載ってますよ。
LinuxＳａｌａｄ
ここの記事が無ければUbuntuに完全移行しなかったかもしれない・・・。

それとプレイヤーですが、Ｔｏｔｅｍは非常に重いのでＳＭｐlａｙｅｒかＭｐｌａｙｅｒがお勧めです。
(ある程度ですが)コーデック内蔵で、動作が軽い部類に入ります(他にもメリットはありますが‥・)。
8.10環境でのウチのＰＣでの話しですが、Ｔｏｔｅｍで動画再生するとＣＰＵ全開になり、再生が追いつかずに一時停止が断続的に起こるので使えません。
なので色々試した結果ＳＭｐlａｙｅｒで落ち着きました。
日本語環境で使える点もＧＯＯＤ。
参考まで。

Linux7さん による投稿:

コーデック云々がよくわからず

私はＬｉｎｕｘＳａｌａｄさんの記事を読み漁って必要な物を入れました。
オーディオとビデオの再生！各種コーデックを揃えよう！。
ファイルの圧縮と解凍！各種アーカイバを揃えよう！。
代表的な物だけ挙げておきますが、見やすくて解り易いので全記事を読むと良いでしょう。
基礎と一歩踏み出したレベルまでならほぼ網羅してあるし、見やすくて解り易いですよ。
コマンドは全部コピペでおｋ(他サイトでコピペして導入したらおかしくなりましたが、ここは大丈夫)。

オフトピですがアーカイバで思い出したので一つアドバイス。
アーカイバは.tar.bz2が.ｒａｒと同等かそれ以上の高圧縮率を誇るので良いですよ。
時間もそれなりに掛かりますが、rarと大差ないのでお勧めです。
画像を入れたフォルダを圧縮しておけば、解凍しなくてもＣｏｍｉｘで閲覧可能。
中身の確認だけなら解凍もビューアも要りません(写真集の閲覧などに便利)。
Winユーザーには嫌がられるので、渡す時はｒａｒにしてあげましょう。