Hey loomy. Welcome to the forums!
I had a problem streaming MKV files to my TV as well. In my case, I didn't have a PS3 or allshare software, so my methods might be different from what you have... Perhaps my methods may prove to be a useful alternative for you.
I wanted to stream MKVs through my Xbox 360, so I got a Windows based computer with Windows Media Center installed. Then I installed the CCCP codec pack
http://cccp-project.net/download.php?type=cccp, the SHARK codec pack
http://shark007.net/ (just select the appropriate one for your OS, followed by the 64x add on if running Win Vista or 7 x64 bit edition), and the DIVX codec pack
http://www.divx.com/downloads/divx, in this order. Then restart the system and connect your Xbox to Windows Media Center, and you should be able to play MKV files, though getting subtitles to work was a crapshoot.
I found this method to be a bit of a pain, and the streaming itself wasn't great for files over 1GB, so I purchased a Western Digital Media Center
http://www.wdc.com/en/products/products.aspx?id=320.This was an excellent purchase for me, as it plays MKV files of any size without difficulty. You can also enable language settings and toggle subtitles with ease. It even streams directly from Hulu, Youtube, Facebook, Netflix, Blockbuster, and Pandora if you enable those options. This does cost some money (my media center was $125), but I'd say it was worth every penny. Using the media center instead of inserting BD or DVDs each time is real nice!