I would make sure Ubuntu was uptodate… ie update and upgrade
Then I would try apt-get install -f
More than once.
Then I would purge the ubuntu-restricted-extras package
and attempt a fresh install.
Then if it still fails, I think the package really is broken… you either complain or try an earlier version or wait for a fix in a later version.
Also read this
If that is correct, you need to install from source code.
but
I am dubious about this… I dont see why anyone would make a binary package that can not be installed, and if it really is a licence issue I dont see how installing from source code would help.