There is an old Mac app called Dumpster that allows you to view and edit Quicktime movie atoms. Ages ago I came across a tutorial online on how to fix the "invalid movie atom" problem using Dumpster, but I've lost the url and have never found the tutorial since through Google. Dumpster can still be found, I believe.
For me, it's easier to re-encode the movie or try "optimizing" it with Subler.
More info here on QT movie atoms:
http://developer.apple.com/library/mac/#documentation/QuickTime/QTFF/QTFFChap2/qtff2.html#//apple_ref/doc/uid/TP40000939-CH204-SW1
Update:
Okay, I found a thread that gives more detailed instructions on how to possibly fix an invalid movie atom. This one is for .mov files but will apply to .mp4 if you're using Atom Inspector. You're going to want a good file to compare to the bad one. Ideally, you want the good movie file to have been encoded with the same parameters as the bad one. If it's a torrented movie, they sometimes come with an included sample of small file size.
Get a program called "Dumpster" from Apple. If you've got a Windows machine you can only get an older/legacy version AND you'll have to register with their "Developers" group first. The Mac version is much easier to get and is much more recently updated...
This app will "dump" the resource/structure of the various types that are used in a .MOV file. Things like the MooV container itself, headers for the kinds of streams included in the container, then the metadata for each stream, then the actual contents of each stream (usually packetized into regularly-spaced sections).
Get to know the structure on very familiar terms, including the usual placement/order and length of each of these things. Use KNOWN GOOD files with predictable material in them as examples (and also for boilerplate for later).
At the same time, get a good HEX Editor application so you can see the direct binary/hex code in the file, unobstructed by its "formatting".
Look at the SAME GOOD file in both apps and familiarize yourself with how the "atoms" are placed. Sooner or later, you'll be able to recognize the hexcode signature of a particular setting or attribute, as well as get an understanding of the relationship between the various packet lengths and the notation used to describe them. This will come in handy when you need to add dummy/filler for a bad section.
Now, try the BAD file in Dumpster. If you're lucky, it'll at least open without too much fuss and you'll be able to see SOME settings, etc. Map those to their placement in the file as seen by the hex editor (which will open ANYTHING--good or bad). Once you've eliminated the GOOD, you will have narrowed down the BAD and you be able to do a trial and error of various settings, etc. Plus you can copy and paste (from another instance of HEX editor using a good dummy file) to use as "backfill/padding" of the bad file so that it MAINTAINS THE SAME LENGTH, and DOESN'T INCLUDE BAD DESCRIPTORS (especially as regards placement and length of the streams).
After a while, you should have a playable file---with some hiccups. This can then be used as a source file in a converter/editor so you can finally be left with a regular file that only has the good stuff.
Source: http://forum.videohelp.com/threads/275665-Trying-to-fix-a-mov-that-was-corrupted-after-using-undelete-software