I spent some time implementing Theora video recording via libtheora. My implementation is currently quite slow, mainly because of two things:

1. I'm rendering off-screen at the specified video resolution, rather than simply grabbing the current framebuffer and scaling. This yields higher quality, but at a much reduced recording speed.
2. My RGB to Y'CbCr 4:2:0 conversion uses floating-point calculations and no SIMD.

As a result, my frame-rate drops to about 4 fps during recording. Here's the YouTube video (poor quality), and the original video (16 MB). The original video seems to crash the Theora DirectShow filter, but it plays fine under MPlayer.