I've downloaded all kinds of codecs and nothing seems to work.
You are probably on the right track there, but I'm not sure how well Movie Factory works with 3rd-party codecs. As you may know, AVI is a "wrapper" or "container" format, and it can contain any type of compression. (If you can play the file on your computer, there is already a compatible codec on your maching.)
You can try using a 3rd-party program to convert your file to MPEG-2 before bringing it into Movie Factory
SUPER is a FREE universal video-conversion program that might work for you.
FYI - It's not ususual to have a file that plays OK, but causes trouble when you try to edit or convert it. This seems to be more common with the more compressed formats. The most reliable way to make a DVD is to start-out with a good MPEG-2 file (DVDs are MPEG-2) or with an AVI/DV fie (13GB per hour from a MiniDV camcorder).