Generic linux distribution pms-generic-linux-unix.tgz (except ubuntu package) has the major downside of not including the ffmpeg, mplayer and mencoder binaries... that's why half of the time, errors are due to old versions your system is using... PS3 Media Server needs specific pre-patched and tested builds of these tools (especially mencoder) to work correctly! As a bare minimum ps3mediaserver needs standard 2011+ builds of these tools.
If you are using Ubuntu based distribution install PS3 MEdia Server with this package viewtopic.php?f=3&t=13046#p62621 It includes every required binary.
For other distributions see this thread viewtopic.php?f=3&t=14605 for installation instructions or compile tools yourself with provided scripts.
PS: If anyone is skilled enough to make packaging of ps3mediaserver for other distributions out there (good luck), well I'll be happy to help :p