There is a patch for libtheora 1.0 alpha3 that makes theora encoding much much faster on CPUs that have MMX.
Created attachment 42417 [details, diff] libtheora mmx patch
doesn't play nice with non x86 systems. Please send it upstream and make sure it works for everybody.
It is already upstream, check xiph's svn