I tried Deinterlacing, but the video still looks like this. Any advice? Could it be the DVDs I'm using or is it just this program?
Difficult to say. If it happens with your every video, then it's the software, if not - the video itself. To make a comparison you can try some other burner. I'm using Free Video to DVD Converter
People say Nero is a good program too.
Please, try to play some other file. If you still encounter problems, try to use another burning tool (ImgBURN, Nero, Ashampoo Burning Studio, etc.).