No luck here. Sorry. A more interesting question is: "What is keeping this from working properly?" I suspect it's either the X-Window-System build or the display drivers, but I have no tangible evidence of this.
More generally, since Debian is not nearly as optimized as cacko, this is probably a good reason why it doesn't work as quickly.
ffplay seems to work slightly better than mplayer for me with the SDL driver, but not worth trying really.
Some people claim to have success using the "-vo fbdev" switches in mplayer from outside the X-Window-System. This *does* work better, almost acceptable especially with 320x240 vids, but I still think this is pretty low quality, and killing X to watch a video is not pleasant for me.