Como aconteceu de eu ter o mesmo problema com outro pacote, querer reinstalar e todos os métodos nas respostas não fizeram nada ou primeiro desinstalar o sistema inteiro antes reinstalar, acabei com uma solução.
sudo aptitude reinstall libebml3:i386
Naturalmente, deve haver outra solução para forçar um pacote a ser reinstalado usando o apt-get em vez do aptitude.
sudo apt-get install --reinstall libebml3:i386