It was libavcodec-extra which I presume isn't a dependency, or otherwise the stock Ubuntu ships with broken dependencies out of the box but I'd find this extremely unlikely.
It's just so strange. H.264 decoders are free now, because Cisco buys a huge unlimited license for their good software decoder every year, maybe Firefox doesn't have the ability to link against that?
Shipping a web browser package without a functioning H.264 decoder, for most people, is like shipping a kernel without mouse drivers.
The terms of Cisco's patent license are tricky. Basically, you must use binaries built by Cisco. Even though the source is available, Cisco's license only extends to binaries they build. If you build the code, you are not covered by Cisco's MPEG/H.264 patent license.
Cisco also only builds a limited number of architectures and platforms.
All of these things make it difficult to depend on for open source projects like Firefox.
Shipping a web browser package without a functioning H.264 decoder, for most people, is like shipping a kernel without mouse drivers.