Out of the box, PowerPoint 2010 will not play mp4 files or even files that have been converted to AVI that may still contain MP4 codecs. The relatively simple solution is to install Apple Quicktime. Even though you're able to play MP4 videos through Windows Media Player (without Quicktime installed), PowerPoint still won't play the videos. After installing Quicktime (which no longer installs with iTunes), the videos played normally.
As per Microsoft, the best format for inserting videos into PowerpPoint 2010 is WMV.