Chances are its because of the files that got included into the MKV file itself.
On my Sony BDP-S580 it plays the numerous MKV files (via PS3 Media Server) that I have which use .h264 video and .ac3 audio with no problems what so ever. Although I do have one file that is of the same show that will not play and has the (Mencoder) tag attached to it. It appears it is because in addition to having a .h264 & .ac3 audio stream it also has a .srt subtitle file which apparently can't be played without using Mencoder to transcode it on the fly. So I had to open the MKV file extract the .h264 video, .ac3 audio, & the .srt subtitle file using . Then put the file back together without the subtitle file making the need to transcode it void.
Here is what I mean:


So either you'll have to find out what you have in your MKV file using MediaInfo and consider taking the file apart if need be or allows PS3 Media Server to transcode the .mkv files on the fly that have more than just an audio & video source.
I prefer using MKVExtractGUI2 (apart of MKVToolNix) to take the MKV file apart. Then use MKVToolNix with to put the .mkv file back together only using the video and audio leaving out the .srt subtitle file. Not only does it take less than 5 mins, but I prefer it greatly to transcoding and using extra resources in doing so. It sounds like a lot to take apart the file and put it back together, but you actually spend more time installing the 3 programs than you do deconstructing / reconstructing them.
MKVToolNix:
http://www.videohelp.com/tools/MKVtoolnixMKVExtractGUI2:
http://www.videohelp.com/tools/MKVExtractGUI-2MediaInfo:
http://www.videohelp.com/tools/MediaInfoTwo other things... You can also just disregard the subtitles (if you find that is your issue preventing playback) by disabling them through the transcode settings. If you notice issues with the audio you can also find that info through MediaInfo and then change the transcoder to match whatever the audio stream is:

Just make sure you always hit the "Save" button before you restart your server otherwise you'll be beating yourself up asking why something isn't working only to find your changes weren't written because the save button was never hit and the changes weren't automatically saved by hitting the restart the server button.
If you need any help doing this shoot me a PM through these boards and I'll be glad to help any way I can.