I couldn't say what problem you are having, but I also recently downloaded some .avi files that seemd corrupted, would not play using mplayer or vlc or totem. I burned the files on a CD and tried to play them under windows xp -- most of these "unplayable files" apparently were made using DRM software (microsofts digital rights management) and windows media player offered to "upgrade" itself to include DRM features and to try to get a "license" for me to view these files. One of the files (when trying to playback with windows media player) opened a website requesting my email address in return for a license.
I don't know if any linux video playback software handles DRM features, and I don't know if I would WANT to get a "license" anyway...
YMMV, this may have NOTHING to do with your .avi problem.