I have the 400mhz version and video's work great! I am using pocketMVP .8m as the player. I encode my videos with Divx 5 codec at 200 kilobit/second output (2passes) with 32 kBit/s, 22,050 Hz, mono sound. Ohhh make sure you rotate the video also. It takes some of the stress off the processor if you pre rotate. Pocketmatrix
http://www.poketmatrix.com has a guide that is where I started and works great. Let me know if anyone still needs help.
PS: I play my videos from a 256mb SD Sandisk.