When Movie Studio gives this message it means the video is QuickTime (QT) encoded format or a PNG/JPG encoding and requires QuickTime for Windows installing. When installing, only install the items that are selected by default.
Download and install MediaInfo and analyse one of the clips and post the results, see this tutorial on how to setup MediaInfo and analyse a video clip for all the data required.
MP4 is not a video format, it is a 'Container' file format which can have several different types of encoding formats for both video and audio.