WebM had an easier path because Google had already written an AltiVec decoder that no one was using. Like the nanojit, it was just a matter of dusting it off, finishing it up and polishing it.
The libtheora in 4/5 does have some hooks for SIMD, but they would have to be written from scratch, and it does not appear to accelerate its own YUV->RGB conversion, whereas we have almost all of these pieces together for WebM already. I'm working on squeezing out more bandwidth from the YCbCr->RGB conversion that WebM uses, which right now is a naive conversion of the MMX routines and wastes about half the vector bandwidth, but this is a solved problem. Playback is a lot better on G5, nearly perfect on quads, and significantly improved on 7450. Even 7400 Macs can at least play the audio even if the video is a slideshow. WebM has come a long way since TenFourFox 4.0.
More to the point, and this might be just the circles I run in, Theora seems stillborn as a format to me. VP3 compresses worse than VP8 and doesn't really have any content weight behind it; most web video seems to be either H.264 or WebM. It would be a lot more work to get libtheora AltiVec-converted and I'd have to have assurances there would be a payoff, since (let's be honest here) I'd be doing most of the work myself. Unless you have a patch ;D
However, I find it ironic that it is sooo close that it is (from what I managed to gleam) rather easy to port to PPC and Altivec. It is even more ironic how Wintel's is half as good as 8 year old Altivec (64 vs 128 data lines).
I'm no Intel arch god, but here's how x86 SIMD breaks down. Intel gives you now three major choices: MMX, the original x86 SIMD; SSE; or SSE2 and successors. (There are actually others, but these three are the most widely used and available.)
MMX aliased FP registers into 64-bit SIMD "MMX" registers, which was a blessing in that the operating system needed no special support to save registers in context switches (so it was instantly compatible), but a curse in that it was integer only and you lost your floating point registers temporarily. Every CPU from the Pentium MMX and Pentium II on has MMX, so there is a lot of MMX code out there. MMX code is hard to translate to AltiVec because it only deals in 64-bit quantities and is typically only aligned to 64-bit quantities, and AltiVec performs significantly worse with misalignment. The current YCbCr->RGB code, because it is descended from MMX code, is only doing 64 bits at once and has some ugly gyrations to deal with alignment. I'm rewriting it, now that I know it works and already is beneficial, to grab two "MMX" operations at once and smush them together into one big vector, saving some steps.
SSE adds new 128-bit XMM registers which are the same size as the AltiVec 128-bit vector registers, but can only deal with them as 4 32-bit floating point quantities. However, AltiVec can do this too, so SSE code translates pretty easily to AltiVec. Strict FP usage isn't generally useful, however, so there isn't much pure SSE code unfortunately.
Most new code is SSE2 and successors. SSE2 adds pretty much all the other data types to the 128-bit XMM vectors, including byte, short and word, and one that AltiVec does not have, 2 64-bit doubles (but this usage is pretty rare so far). SSE2 code is a bit harder to translate to AltiVec than SSE because SSE2 is not as picky about misalignment and the AltiVec C intrinsics require strict typing or a lot of casts, where it is a common idiom in SSE2 code to just treat the vector as a blob and sling it around transparently from type to type. But, again, strict typing saves you from stupid mistakes, so choose your poison. SSE3, SSSE3 and SSE4 just add more instructions.
SSE2 is a lot more comparable to AltiVec than SSE or MMX, but AltiVec still has some great features SSE2 doesn't have. In particular, AltiVec's permute unit makes it possible to turn certain kinds of swapping and reordering operations into a single instruction which runs very quickly. I use permutes to instantly deal with endian swaps. And most important of all, there are lot more AltiVec vector registers than SSE2 XMM registers, even if the x86 chip is in 64-bit mode.
AltiVec is remarkable technology and of course yet another wonderful thing about the PowerPC that never achieved its full potential.