Eu tive o mesmo problema que você (exceto que estava trabalhando no 13.04 por um tempo, até que algo mudou). A solução para mim foi felizmente simples:
sudo apt-get instala o chromium-codecs-ffmpeg-extra
Isso substituirá o pacote chromium-codecs-ffmpeg pelo acima. Espero que funcione para você, aproveite Pandora! :)