reuben,
You probably need to convert to .AMV video's.
Your player can't play straight .MP4 or .AVI mp4 files, it needs to be converted.
You also need the
AMV Convert Tool 3.68 (MP3 Player Utilities 3.68) instead of the 3.57 (as that only converts to .MTV files instead).
Download it from
here.
Make sure you also have the codec pack, DirectX and Windows Media Player 10 or above installed beforehand otherwise you will get problems converting.