I like HandBrake, but there are several others like AcidRip, WinFF and even
VLC will transcode videos.
Handbrake: www.getdeb.net/search.php?keywords=handbrake
AcidRip: http://untrepid.com/acidrip/
WinFF should be in the repositories, but is also found here:
http://winff.org/html/
VLC is in the repositories.
If you like commandline (I don't) then you can use mencoder. see:
http://www.linux.com/archive/feature/121385