HandBrake is an open-source, GPL-licensed, multiplatform, multithreaded video transcoder, available for MacOS X, Linux and Windows.
Screenshots:
http://handbrake.fr/screenshots.php
Package:
Qt: http://thenktor.dyndns.org/packages/xap/qhandbrake/
Gtk: http://thenktor.dyndns.org/packages/xap/ghandbrake/
Notes:
Building this package was a bit picky

* I've chosen to use "--arch=i686 --optimize=speed" as configure options, which should result in "-O3 -march=i686". "-O2" is not available via configure option. I certainly can tweak it to O2 but I think it is not necessary.
* During build it loads dozens of other multimedia packages. I guess it links all of them statically and it is ok this way.
EDIT: Gtk version added. The Qt version segfaults on my PC.