I know this thread is a bit dated but I have done a bit of research trying to get this working as well. What I eventually discovered was that MP4s had to be structured so that they were "web optimized." If you are encoding video files in HandBrake, use can check the Web Optimized box to use the --optimize command.
What this does is rearranges the MP4 files so they play better over the web as progressive downloads. Basically, doing this moves the MP4 atoms to the beginning of the file instead of the end, which assists with faster start of streaming playback from certain devices but makes changes to the atoms less efficient (metadata, etc.).
There are a number of utilities out there that can move the MP4 atoms. However, the ONLY one I was able to successfully create consistent playable MP4s with is AoA MP4 Patch. (google it)
I thought I would have to re-encode all of my MP4s with they wouldn't play back via DLNA to my Samsung TV. But, after running them through the AoA MP4 Patch utility, they all now play successfully.
Best of luck to you all!
Josh - just wanted to say thanks for this info.
I'd given up trying to find a solution to it and just played my MP4s via the PS3.
I used AoA's MP4 patch utility on one file and successfully played it back on the TV
However, there is a slight issue in terms of fast-forwarding. It seems to start skipping frames when resuming playback.
Anyway, I've also now adjusted my Handbrake presets to include the "Web optimized" option.