Viele Encoder schreiben die MP4-Dateien unsauber und setzen den Index an das Ende der Datei und nicht an den Anfang, daher muss der Flashplayer zunächst die gesamte Datei laden um das Video streamen zu können.

Um diesen Fehler zu reparieren benötigt man das Tool qt-faststart.

Das Tool bekommt man hier:
Klick mich

Einfach via: easy_install qtfaststart installieren.

Wenn das Tool installiert ist, dann müsst ihr qtfaststart nutzen und nicht qt-faststart. Letzteres Tool ist für MOV-Dateien gedacht.

Die Syntax ist selbsterklärend:

Usage: qtfaststart [options] infile [outfile]

Vielen dank an:
http://videoencoding.websmith.de/encoding-praxis/linux-qtfaststart-metadaten.html
und natürlich an
https://github.com/danielgtaylor/qtfaststart