O problema foi que o pacote playonlinux
tem dependências que possuem suas próprias dependências. Então, adicione os pacotes not going to be installed
à lista de instalação principal.
sudo apt-get install playonlinux python-wxgtk2.8 mesa-utils primus-libs