Ich glaube die rechtliche Grauzone besteht nur bei DVDs und mp3s. Bei mp3s geht es aber meines Wissens auch nur um kommerzielle Nutzung.
Außerdem gibt es inzwischen einen kommerziellen DVD-Player unter Linux.
Zur eigentlichen Frage:
Kaffeine ist nur ein Frontend für verschiedene andere Programme, die dann im Hintergrund die eigentliche Multimedia-Ausgabe vornehmen. Das bedeutet, dass Kaffeine das abspielt, was das jeweilige Backend abspielen kann.
MPG-Videos sind kein Problem, bei AVI kommt es darauf an, was darin enthalten ist (ist nur ein Container-Format). Wenn da z.B. divX oder Xvid drin ist, stellt das kein Problem dar. WMV ist nicht ganz einfach, weil es ja von Microsoft ist, aber bis WMV9 hat man eigentlich nie Probleme, aber bei WMV10 hakt es oft (oder geht gar nicht? Konnte ich bisher nicht einwandfrei feststellen - bei mir hat's nie funktioniert).
Die meisten anderen Videoformate lassen sich eigentlich auch abspielen. Man muss nur für manche etwas mehr basteln bis sie laufen als für andere.
DVDs sind wie gesagt in der rechtlichen Grauzone, außer man kauft einen Player. Das Problem dabei ist, dass DVDs in der Regel verschlüsselt sind (als Kopierschutz) und wenn man die DVDs nicht mit einem dafür vorgesehenen Programm entschlüsselt und wiedergibt, umgeht man den Kopierschutz möglicherweise widerrechtlich. Deswegen kann ich dir dazu nur sagen, dass es funktioniert, nicht schwierig ist und wenn du es auf deinem PC nur dazu verwendest DVDs anzusehen und sie nicht kopierst, wirst du vermutlich nie rechtliche Schwierigkeiten haben, aber eine Anleitung geben kann ich dir nicht, weil ich dann das Forum und mich in Schwierigkeiten bringe.
Wer den kommerziellen DVD-Player für Linux angeboten hat, weiß ich grad nicht, aber das wird hier sicher noch jemand erwähnen. Damit wärst du dann auf der sicheren Seite.