Eu resolvi o mesmo problema instalando hplip
manualmente. Executar:
sudo apt-get install hplip
e, em seguida, execute:
hp-setup
que abrirá uma GUI na qual você poderá pesquisar / adicionar sua impressora.
Você também pode instalar diretamente a GUI por:
sudo apt-get install hplip-gui
Execute o traço e siga as instruções.