The problem is PowerPoint, which seems to be very picky with videos. MP4
videos won't run in every PC configuration, so there's only two things that
will definitely work: MPEG & WMV.
You could try the trialware – VidLogo in order to convert your videos to
MPEG or WMV. This would be the best choice, I guess.