QuickTime Doesn't Recognise Some MP4 Files

When opening an MP4 file with QuickTime Player I get this:

The movie's file format isn't recognised. To see if additional software is available that will enable QuickTime Player to open the movie, click Tell Me More.

When I click on Tell Me More, it navigates me to this: http://support.apple.com/kb/HT3775?viewlocale=en_US

where it shows that MP4 files are supported by QuickTime. So I don't understand why I get this message when opening some (not all) mp4 files.

I've also tried VLC, NicePlayer, Flip Player, DivX.

I have been searching for a solution to this problem but I didn't find any, I have Perian installed but it doesn't seem to work properly because it should play MPEG-4 files via QuickTime but it doesn't.