If you dont get Avidemux working, here are some alternative methods.
In the Terminal run:
sudo apt-get install ffmpeg winff
Just plain FFMPEG
WinFF is probably the most user-friendly tool for converting videos and extracting audio from videos in GNU/Linux. Avidemux is a popular and useful video editing application, which makes it quite simple to cut and crop videos to your liking, and much more.
Tip: To make a video for a mobile phone in WinFF, select 3g2 as the type of video you want to make, but change the extension from ".3g2" to ".mp4" when the video is complete. To increase the audio quality of the video, click on "Options" within WinFF, and in the option labelled "Audio Bitrate", type "96000" (default is 64000, which is 64kbps). However, your phone may not play it properly with the audio at 96kbps, depends really. Test it yourself.
Enable Medibuntu repository.
In a Terminal run:
Download this script and save it to /tmp
sudo apt-get install ffmpeg
In a Terminal run these three (3) commands one at a time.
Then the command to convert the video would be:
sudo apt-get install gpac
sudo mv /tmp/pypodconv /usr/local/bin/pypodconv
sudo chmod +x /usr/local/bin/pypodconv
This by defaults to a 200kbit/s 320xNNN 2-pass H.264 video, for iPod viewing. If you want to make 500kbit high-definition encodes:
pypodconv -i INPUT_FILE -o OUTPUT_FILE
pypodconv -i INPUT_FILE -o OUTPUT_FILE --hd -b 500