Have you tried using just plain mplayer to play videos? That's pretty much all I use and I can play just about anything in my library with good speed. Even over sshfs, which involves streaming the video and encrypting/decrypting traffic at the same time. Canola uses mplayer also, if it's installed, although it seems a tad less efficient that way.

I guess what I'm getting at is that I've never had very good luck with playing videos on the default media player.

Also, you can start up the terminal application when the device seems to be getting slow and use the command 'top' to see what's using your CPU.