Então, fui em frente e instalei playonlinux
apesar de todos os problemas de dependência. Acontece que não foi problema reinstalar todos os pacotes depois. Eu ainda não entendi muito bem por que isso foi necessário em primeiro lugar.
O comando de reinstalação que usei para sua conveniência:
sudo apt-get install alien cdbs debhelper dh-make dh-translations gettext google-earth-stable intltool intltool-debian lsb-core po-debconf
Edit: Esta parece ser uma ocorrência bastante comum ( ex 1 , ex 2 ) no Precise. Aqui está um bugreport no launchpad.