Hello Kris,
Just a thought, even though the files are named MP4 it is possible that they still don't fit your NWZ-S616F requirements.
To convert WMA's or Mp3's to MP4's that will play on my iPhone I use a free convertor program called SUPER. It is very easy to use and once you select the conversion to MP4 you can ususally just use the default settings for the video and audio.
I would try downloading the SUPER program and try running one of the files that won't play through the convertor and see if when it is done encoding the file plays.
If you want to give the SUPER program a try
HERE is a link to the free download.
All I can think of at the moment. Please post back with any progress.
Joe