I installed lmde today and I am alos having similar problems playing back h264 mkvs. I have tried what was suggested above but it didn't work; I have tried vlc, mplayer and totem with them crashing with a segmentation fault, but mplayer does tell me this as it breaks:
MPlayer interrupted by signal 11 in module: filter video
vlc warns me about my audio codecs on startup:
Potential ALSA version problem:
VLC failed to initialize your sound output device (if any).
Please update alsa-lib to version 1.0.23-2-g8d80d5f or higher to try to fix this issue, but i believe my alsa lib is 1.0.24 already...
All players crash when subtitles are to be displayed. The only way I've got anything to work is to run mplayer from the terminal.
Any thoughts would be greatly appreciated, thanks