
The only time I've seen any "stutter" when doing things (generally audio playback) was when I was doing heavy disk I/O (downloading GPS maps in the background over WiFi). What is the storage for your videos? I think the internal NAND is actually pretty slow, perhaps a high-speed (Class 10 / Ultra 1) Micro SD card would be worth trying because it might be faster? Having worked a lot on embedded systems, eMMC/SD is often a TON faster than raw NAND flash, even assuming high speed grade parts all around - what is on your phone is likely eMMC. Assuming it actually is NAND flash and is not just named NAND flash, that likely is why. We also don't know how it is formatted, specifically. For example, if they used JFFS2, it compresses better but is way slower than, say UBIFS. Similarly, if they used a block device emulation so that they can use ext3 on top of UBI on top of NAND... well, that's just a lot of layers of the onion, and I imagine it to be slow (I haven't tested this on any of my designs, so I can't say).
That's probably more information than you cared to know, but try video from a high speed grade Micro SD card. Also, try a DVD. If it can play a DVD smoothly, then it's a storage data transfer rate problem, not a CPU/RAM problem (that CPU should be quite adequate for the task).