iImage Information

FFmpeg is the best open-source video converter out there. It is plain, simple, but very powerful. FFmpeg is a command line program. There are a few graphical frontends too, but they tend to be buggy. So, the easiest way to convert video in Linux is using FFmpeg in the terminal (Linux command line).
Step 1Opening the terminal
iImage Information

Terminal is in the applications menu in one of the sub-categories. (Depends on the distribution and the desktop environment). In Ubuntu, it is in Applications->Accessories->Terminal.
First, cd to the directory, where your video file is (cd means change directory)
If the file is on desktop, the command would be: cd Desktop
if it's in the videos folder, it would be: cd /home/$USER/Videos
Now you're virtually inside that folder.
Convert to VCD format:
ffmpeg -i MVI_1841.AVI -target ntsc-vcd firstoutput.mpg
then I converted it to MP4 format:
ffmpeg -i firstoutput.mpg -s 320x240 video.mp4
**Please note I had to set the size to 320x240 because ntsc-vcd was different and distorted the video**
It worked. Probably not the most efficient way converting the video twice but it does work. Just thought I'd let people know. Perhaps there is a way that works and requires only one conversion :)
Find the frame rate of the input video using:
ffmpeg -i MVI_1841.AVI
then convert with the frame rate parameter set to that of the input video. In my case it was 15. Use this command.
ffmpeg -i MVI_1841.AVI -r 15 output.mp4
This way only one conversion is needed.
There are some other interesting things you can do with ffmpeg beyond simple video encoding, like extracting still frames from a video and adding/extracting an audio track to a video file.
2) There is a windows version as well.
To add:
For help on ffmpeg run:
ffmpeg -h
to specify an audio codec add the argument
--acodec codec'
to specify the video codec add the argument
--vcodec codec
to check the codecs that you can use with ffmpeg, check
ffmpeg -formats