Ich weiß nicht, ob es da große Unterschide zwischen den Versionen gibt, ich bin selbst erst seit ca einem Monat Ubuntu User. Das, was ich sage, basiert also auf 7.10.
Für mp3 würde ich perönlich dir XMMS empfehlen, das ist stark Winamp nachempfunden und ich finde es bisher ganz gut und habe auch noch keine Probleme gehabt.
Und für Videos und so ziemlich alle anderen Formate sage ich glaube ich nichts Falsches, wenn ich dir den VLC Media Player empfehle, der sollte bereits vorinstalliert sein.