What would it take to create a free codec rivaling H.264? Is it a patent issue or a technological one?

It seems to be mostly about patents. The H.264 patent pool contains hundreds of patents owned by 23 organizations. Many of them appear generic enough that any new codec would run a serious risk of infringing them. For example, one of H.264's major improvements over previous codecs is the use of arithmetic coding, and there's a patent in the pool concerning a "method and apparatus for binarization and arithmetic coding of a data value".

(Here's an interesting mini white paper about the codec patent situation: http://www.vcodex.com/videocodingpatents.html )

Worse, there's the possibility of submarine patents that are not included in the H.264 pool. Qualcomm has already attempted to sue Broadcom for making H.264-compliant products that allegedly infringed Qualcomm patents (which Qualcomm had not disclosed when H.264 was being developed). They lost the case, but the US Court of Appeals specifically limited the scope of those patents' unenforceability only to products which are covered by a H.264 license. That means Qualcomm is still free to sue for any independently developed non-H.264 codecs that might be similar enough.

but would people perceive it as being a "low fi" alternative given they are used to the higher quality now? (sure it worked in the past, but we will see).