The key is what CODEC is in that file?
MP4 is a highly compressed format that is, generally, made for viewing and not editing... more info at http://www.pacifier.com/~jtsmith/ADOBE.HTM#edcf
A link with many ideas about computer setup http://forums.adobe.com/thread/436215?tstart=0
Work through all of the steps (ideas) listed at http://ppro.wikia.com/wiki/Troubleshooting
If your problem isn't fixed after you follow all of the steps, report back with the DETAILS asked for in the questions at the end of the troubleshooting link
Yes, AVCHD is not easy to edit, and requires a powerful, properly setup computer (see link above)
Convert AVCHD to HDV http://forums.adobe.com/thread/390605?tstart=0
MP4 is but a "wrapper," as John mentions. It is like .AVI, .MOV, .WMV, etc., and can contain all sorts of CODEC's (the "building blocks" of AV files). This ARTICLE will give you some more background on those "wrappers," and how to peek inside them. For a primer on CODEC's, this ARTICLE will give you some useful links.
For your MP4 files, it is very likely that they are not created equal, and differ inside. It might be the CODEC, or implementation of the CODEC.
In a perfect world, one will work with footage from the same camera. With footage from several sources, one has a challenge ahead, and conversion might be the only way to solve the issues.
BTW - the PrPro-Wiki is a great resource, especially for someone starting out with PrPro. Most of what one would ever wish to do, is in there in either the FAQ's, or the tutorials.