Yes you can accelerate it, either by optimising the ARM code used by mplayer (and I understand that there is quite a bit of room for optimisation there) or by passing off some or all of the decoding to the DSP (by writing a DSP task and ARM-side wrapper).
Transcoding with ffmpeg2theora, by using preset "padma", I've got every video working in reasonable speed. Code: $ ffmpeg2theora --preset padma anyfile.xxx
$ ffmpeg2theora --preset padma anyfile.xxx