Won't play my video files

[Trunkin]

I've tried using Avidemux and Handbrake to convert my files, but Ikeep getting the same message, "Non Supported video format". I tried converting the files with AAC/MP3 audio, H.264 and MPEG-4 video. None of the combinations work. I'm starting to get really frustrated, I have no idea what I'm doing wrong. One of the main reasons I bought the player in the first place was the supposed ease of use when it comes to video converting/playback, but I'm having more trouble with this than I ever had with the iPhone. I must be doing something wrong, because normal avi files work just fine, it's only when I try to convert them that I get the error message.

EDIT: My operating system is Linux Mint 9, but I've also tried it with Ubuntu.

[lebellium]

Here are the detailed video formats that are compatible
Make sure you are in fw 2.22 too.