Samsung Video Format

Ok guys so I need your help. I have a SAMSUNG LIBRE C3300 and have been trying to put videos on it by downloading them from the internet, onto my computer, then onto my phone. I have videos on there which I have taken by my phone and the file format is ".MP4". So I downloaded these videos from YouTube and converted them to .MP4. When I try to play them on my phone, it says "file format unsupported" or something similar. How can it be unsupported when its playing other vidoes of the same format? I also then tried with .AVI, .WMV,.. all the same error.

Please help!!

Thanks