Transcode the MP4 to a standard production format using the Adobe Media Encoder and then try again. I suggest something like Quicktime Jpeg 2000
It didn't work any other suggestions?
Try rendering an image sequence from your original footage then load that into AE and Camera Track the image sequence. Use the AME to or AE to render a JPEG or PNG image sequence:
It's important to know that some footage cannot be Camera Tracked. In order for camera tracking to work there must be a significant amount of fixed geometry in the scene. For example, if you have a shot of open water like this it cannot be Camera Tracked:
This shot also cannot be camera tracked successfully because most of the frame is moving:
If transcoding or converting the shot to an image sequence does not fix the problem and you don't get a frame rate mis match warning then you could have possibly not given enough memory to other applications in you memory and multi processor settings. Keep memory allocation for other apps in even numbers and make sure that you have not starved the dynamic link server that does camera tracking. If you have the memory 4GB to other apps is absolutely the minimum. If you only have 4GB then give 2 to AE and 2 to other apps.