You can manually install the required version of av libraries downloading them from http://www.ubuntuupdates.org/. Search for packages libavutil51
, libavformat53
, libavcodec53
Download the ones matches the architecture of your JVM and use sudo dpkg -i libav*.deb
to install them.