I tried qt-faststart with my own MP4 (h264+AAC) encoded files and was always getting an "last atom in file was not a moov atom" error message (and no output file). I was then assuming my files were ok and searched for the problem elsewere. After hours of testing, my assumption proved to be wrong - indeed, it seems my files had no moov-atom at all, not at the beginning nor at the end!
To succesfully fix this I used ffmpeg first to "regenerate" the file - that is, remux the original h264+AAC tracks into a new MP4 file without reencoding it:
ffmpeg -i souce_file.mp4 -acodec copy -vcodec copy target_file_1.mp4
After this, the new file should have its proper moov-atom at the end. So now you can use qt-faststart in order to move it to the beginning, as Kit explained in his answer:
qt-faststart target_file_1.mp4 target_file_2.mp4
After doing that, mediaelement plays all my videos just right after clicking on the play button, when the file starts downloading! :)
If your problem is you already have all your files in a youtube-like site, your hosting is Linux-based, ffmpeg is not there and you cannot compile it on your own, you my find it useful getting a static build of ffmpeg. You can find that here:
http://ffmpeg.gusari.org/static/ (32 bit)
or here:
http://dl.dropbox.com/u/24633983/ffmpeg/index.html (64 bit)
Unfortunately, on the 32-bit build I used there was no qt-faststart, not as binary nor as source code. In this case you can download it from ffmpeg SVN and compile it directly with gcc. I did it succesfully in my ultra-el-cheapo shared hosting. It doesn't seem to have any build dependencies. Or you can even try my own qt-faststart binary build and see if it works for you.
EDIT: I've just discovered that in newer versions there's no need for qt-faststart at all. You can encode directly with ffmpeg using the following option:
-movflags +faststart