Parece que talvez o daemon cups não esteja sendo executado na inicialização. Isso é o que aconteceu quando eu tive um problema semelhante. Você pode verificar se ele está sendo executado na inicialização. Como root run
# service cups status
se não estiver em execução, execute
# service cups start
Veja se isso muda na caixa de diálogo da impressora.
Se isso funcionou, ter xícaras na inicialização
# update-rc.d cups defaults
Apenas um pensamento, no meu sistema atual, o daemon é listado como xícaras, mas; se você tentar xícaras e ele retornar
cups: unrecognized service
você pode tentar
cupsd in place of cups