I have always found it a hassle to convert a video file from one format to another in Linux for lack of (or rather, not being aware of) a good Free video conversion suite. I have tried converting an Avi file to another format such as mp4 using some software but the results were far from satisfactory. I take it that it has more to do with the settings I selected than the fault of the software I used.
Axel has written a quite detailed article explaining how to create a custom DVD using a Free video conversion software called DeVeDe. What is really interesting about his article is that he shows the exact settings he used in the conversion - a big factor if you want your converted video file to have more or less the same quality. In fact my experience shows that you need to get the ratio of number of frames per second with respect to resolution of the video right else the quality of the video might suffer.
He has used the Windows version of DeVeDe but this is a software which is available for Linux as well. For example, in Ubuntu, you can install this software using the command :
$ sudo apt-get install devede
You need to have Mplayer, Mencoder, DVDAuthor, VCDImager, MKisofs and all the proprietary codecs installed though since DeVeDe is just a front-end. More over since DeVeDe is a Python script, it requires Python as well. For more details on the actual steps required to convert a video file from one format to another, do read the guide.