First you need to make sure your server can play a video properly formatted for "fast start":
You can download the file at http://vjs.zencdn.net/v/oceans.mp4 and host it on your server. If it works fine (ie video starts before full download) then your server/script config is ok.
If the above works the issue is probably that your mp4 is not properly formatted. You can try to use handbrake or MP4Box to repack your file. You need to activate the "web optimized" option (aka fast start) with handbrake.
For MP4Box (linux): MP4Box -inter 500 yourFile.mp4
More info on this here.