Acho que recomendo uma reinstalação do libtheora0:
sudo apt-get install --reinstall libtheora0
E como você tem algumas barras invertidas não unixey em sua pergunta original, vamos explicitar a procura das bibliotecas:
ls -l /usr/lib/libtheoraenc*