I use alot ffmpeg ,FFMPEG is the swiss-army knife of video and audio format conversion. It succeeds when no other program can. It is free and open source.Normally i install:

sudo apt-get install ffmpeg

sudo apt-get install ubuntu-restricted-extras

But in my system didnt work so i use the
Jon Severinsson's FFmpeg PPA
Open a terminal (you know the drill)

sudo add-apt-repository ppa:jon-severinsson/ffmpeg
sudo apt-get update
sudo apt-get install ffmpeg

I have a nice bash script : to convert from mp4 to mp3 very usefull if you convert videos to sound

for f in *.mp4; do ffmpeg -i "$f" -vn -c:a libmp3lame -ar 44100 -ac 2 -ab 192k "${f/%mp4/mp3}"; done

Convert all .mp4 files to .mp3

for f in *.mp4; do ffmpeg -i "$f" -vcodec copy -acodec copy "${f/%mp4/avi}"; done

Nice gui is the WinFF for all your convertions (the one of the picture is the winff,you can install from the software manager).
More to come for the nice FFmpeg