Tente instalar manualmente os drivers.
sudo apt-get install hplip hpijs
Com versões mais recentes do Ubuntu, hpijs é agora driver de impressora-hpijs, não tenho certeza quando a alteração foi feita, para você pode precisar de:
sudo apt-get install hplip printer-driver-hpijs
Em seguida, exclua e reconfigure sua impressora (de system-config-printer).