Eu vou para a página de suporte da HP e baixo o HPLIP (o que eu mencionei antes) de: link
Eu corro o script com o bash bash hplip-3.17.11.run
e sigo as instruções do modo de instalação automática.
- Versão antiga que eu tinha: HPLIP 3.16.3
- Nova versão: HPLIP 3.17.11
Afinal, foi o HPLIP que faz a minha impressora falhar. Esta é a solução que encontro. Espero que funcione para qualquer um que tenha esse problema!