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.
Shipping a web browser package without a functioning H.264 decoder, for most people, is like shipping a kernel without mouse drivers.
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.