Qubes doesn't use video acceleration as it is less secure.
Mplayer is IMO the best option for video playback in VMs, as it focuses a lot on optimizing without using acceleration.
You can also sacrifice some quality for speed with some of these options:
mplayer -vfm ffmpeg -sws 4 -lavdopts skiploopfilter=all:fast:gray:lowres=3:threads=<number of vcpus assigned to the vm> <file>
You can change the default configuration and/or create an alias in either the template or the dvm/appvm.
I set dropping frames(g key) to enabled, but change to hard(pressing g again) if audio video timing is especially important.
You can also check if assigning more memory and vcpus helps, if you have not already.
Launching many qubes, like qubes updater does, can also cause signifigant stutter with slow drives in my experience.
Also remember that h264 decodes a lot faster.