We ended up watching it on my computer, to save us trouble in the end. xD So for further reference, if I want to watch a .mkv on my XBox after conversion, I'll need another program to make the softsubs hardsubs??
My advice to you is to transcode it with the subs (hardsubbing) and then play it with your Xbox