That's what I was afraid of; I know nothing about codecs.
I went to wikipedia and did some reading on codecs but I still don't have a real clear grasp. I did download a Codec Identification Tool and analyzed the .mp4 that did play vs the converted one. The first one showed: "Codec- avc1, Name- H.264/MPEG-4 AVC" while the converted .mp4 was "Codec- mp4v, Name- MPEG-4 Video", so I see your point about the H.264 format.
Any idea if there is a way to convert .avi, .3gp, .wmv, etc. to the proper codec for use with the HTML5 video tag?