I was having the darnedest time getting MKV files to play from PS3 Media Server from fresh Ubuntu 10.04 Lucid Lynx. They worked fine from Windows and from an old 32-bit 9.04 Jaunty Jackalope system. Turns out Warriorcookie found the problem. 64-bit Linux systems need to install 32-bit libraries (ia32-libs for Ubuntu) for some packages, including Tsmuxer, apparently. So I simply:
sudo aptitude install ia32-libs
Then I rebooted and all was well. WOOHOO!!