Tente:
sudo apt-get install cups-daemon
que inicia um servidor de impressão que cuida da impressão para nós.
Eu comecei a conseguir isso depois de instalar o libcups2, acho que ele desinstalou o pacote acima.
Um sintoma disso é que o sudo service cups start
deve falhar, pois o pacote não está presente.