I have found that the Samsungs are notoriously finicky about playing files not in the
exact formats that they expect through DLNA. It doesn't matter if the format is avi, mpeg, mp4, mkv, etc. The supported DLNA video formats are here:

This was posted early last year on the CNet forums, but I don't think the DLNA formats that Samsung's support has changed much, if at all.
The problem is that Samsung has decided on providing very restrictive DLNA compliance. Beyond this, since they decided not to license DTS, you will most likely encounter "No audio codec" errors, even if the video plays on some mpg and many mkv/mp4 files. You will need a separate DTS decoder for this. In my experience, I've found that there seems to be better success, if the audio is transcoded to AAC format, either on-the-fly using a media server such as PS3MediaServer or prior to viewing using ffmpeg or mencoder.
In my attempts to get my TiVo HD files to play from my ReadyNAS, I've created some scripts using mencoder to convert to mp4 that seem to work quite well through both PS3MediaServer and minidlna. Of course, there are products out there that will do this for you, but I like to control my video/audio quality.

I have yet to spend a lot of time figuring out how to transcode my DVD (in VIDEO_TS/VOB format) library on-the-fly using PS3MediaServer, but I can let people know if I am successful.