Answered my own question. I was using the Xvid codec on my computer (as recommended by the MaLa config program), and that's what was causing the problem. I uninstalled the codec, installed the K-Lite codec pack and the problem went away.
Just leaving this here for others to find in the future.
Also, MaLa CAN handle mk4 videos, but for some reason I needed to change the file extensions on the videos to .avi from .mk4. Then MaLa picked them up and played them.