I have similar problems using Mint 12 x64 with my Radeon HD 6950. Now, it plays x264 MKVs reasonably decent (doesn't matter whether it's 720p or 1080p) IF you do not have anything running OpenGL, like Cairo Dock in OpenGL mode. When you have Cairo Dock in OpenGL mode running, the video acts like the frame rate has been cut by 60%. Mind you, the videos keep up with the sound, but the frame rate is choppy as can be.
The results are the same whether you use MPlayer with the Mint codecs installed or VLC which uses its own internal codecs.
Mind you, in Windows 7 x64, all x264 playback is perfect with this system.
I realize that this is most likely an issue with the closed source ATI/AMD linux drivers, but does anyone have any info that can help?
To rule hardware not being powerful enough out, my system is a Phenom X6 1100T, with 16GB of memory, Radeon HD6950 2GB, SSDs, GbE Ethernet, etc. Plenty of power and bandwidth. Just obviously not utilized/configured correctly...