Também estou tendo um problema semelhante com a impressora HP DeskJet 1xxx (não lembro o modelo exato). Meu entendimento do problema é que a impressora exige um driver proprietário baixado do site da HP - que supostamente acontece automaticamente quando a impressora é detectada, mas o script de configuração geralmente falha - em particular, isso acontece toda vez que uma nova versão do HPLIP é instalado pelo Update Manager.
Para corrigir isso, eu executo o utilitário de configuração manualmente:
sudo hp-setup
Isso fará algumas perguntas (desligue a impressora, ligue a impressora, etc.) e baixe o driver.
Em algumas ocasiões, tive problemas em executá-lo no modo gráfico - há uma opção de linha de comando para usar o modo de texto, algo como sudo hp-setup -t