Faça o download e instale o HPLIP diretamente no site da HP OPEN SOURCE. link
Clique em DOWNLOAD HPLIP. Encontre o arquivo baixado e clique com o botão direito nele e selecione PERMISSÕES. Selecione MAKE EXECUTABLE. Clique em OK.
Clique com o botão direito no arquivo novamente e selecione ABRIR e EXECUTAR. Siga as instruções.
* O motivo pelo qual isso funciona é principalmente porque ele detecta e instala dependências que a versão do apt-get ou do software center não faz.