Jamie Hockin My understanding is that MP4 is a container file format. The video inside the container can be in several different codecs.
Do any other videos play in OpenLP?
Have you tried converting the video (use HandBrake - open source video converter) to another format?
Is VLC properly configured to work with OpenLP?