Toast (commercial software) has always been able to convert just about any format I dropped in it into a working DVD.
There's other free software to convert video formats (google for ffmpegx), but in my limited experience with them, they sometimes require a fair amount of tweaking in order to get decent output.