I don't have any mp4 files but yet the gallery problem persists.
edit: I finally
fixed my Gallery issues:
I was in need of consolidating my pics because of all the various ROMs throughout the lifespan of my Hercules so I moved the DCIM/Pictures/anything else with a *.JPG or *.3GP (didn't have any *.MP4s but would've done those as well) folders themselves to my PC so that they were completely deleted from my internal and external memory on the phone.
I then took a picture as to let the phone recreate the DCIM/Camera directories and proceeded to put all of the *.JPGs back in that one folder but NOT the movies. After that everything was finally solved and I've flashed several 4.3 ROMs to test.
So it was basically a combination of deleting any pic/movie folders and also avoiding both
MP4s and 3GPs when I moved things back from the PC. At least for me, 3GPs were also a culprit in addition to the MP4 issues which others have mentioned.