Video: Not ready to play yet

Hi there, I have a problem with the mp4 videos / movietextures,

it just won't play or display preview, telling me that it is "Not ready to play yet".

Basically it is the same issue and question as this unanswered page http://answers.unity3d.com/questions/542026/movie-textures-not-working-not-ready-to-play-unity.html

But I really need my video to be mp4, and it doesn't work. I tried many encoders, none would work.