Probé todos los métodos encontrados, finalmente lo arreglé instalando un paquete llamado pulseaudio:
sudo apt-get install pulseaudio
Tienes libpulse0 de 64 bits, mientras que el programa que intentas ejecutar es de 32 bits.
En Ubuntu de 64 bits, puede instalar bibliotecas de 32 bits agregando :i386
al nombre del paquete:
apt-get install libpulse0:i386