[Theora] Slowdown on lots of motion

[J.B. Nicholson-Owens]

I'm playing the "Honey" movie (both Honey-small and Honey-large) and I notice
significant slowdown during periods of lots of motion (when the camera shakes,
when the first man hops into bed, when people turn around and approach the
camera, etc.).  The audio plays smoothly all the time but when there is a lot
of motion, the picture freezes and resumes when there's less motion.  The CPU
usage shoots up during high motion video.  I saw this in one of the Creative
Commons pieces (the one with the kids running backwards and Prof. Lessig's
words and voice in the beginning), but it went away when I played the "small"
encoding of the same movie.

This suggests to me that I'm playing movies which require a faster machine to
play.  Is that likely to be correct?  Would it be possible to have a player
pre-decompress frames in high-motion areas of the movie while playing
low-motion areas of the movie and cache them in RAM or on disk so they could
be played back at full speed?  Or would I be better off re-encoding the movie?
I'm just after a way to see the movie smoothly.

I'm using Theora 0.99.12 with xine-lib version 1.0.0 (from the FreshRPM
packages).  I'm running this on Fedora Core 2 GNU/Linux and here are the specs
of the machine:

$ cat /proc/cpuinfo
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 9
model name      : Intel(R) Pentium(R) M processor 1400MHz
stepping        : 5
cpu MHz         : 597.657
cache size      : 1024 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 2
wp              : yes
flags           : fpu vme de pse tsc msr mce cx8 mtrr pge mca cmov pat clflush
dts acpi mmx fxsr sse sse2 tm pbe tm2 est
bogomips        : 1179.64

Any pointers you could provide to help me watch the movies more smoothly would
be appreciated.  Thanks.